Skip to content
The Chat Archive
llama-4-scout-17b-16e-instruct· Meta LMArena Human Preference 140K

Given a string, find the index of the first character that does not repeat. If all…

  1. User

    Given a string, find the index of the first character that does not repeat. If all characters repeat, return -1.

  2. Assistant

    Solution: Finding the Index of the First Non-Repeating Character

    Problem Statement

    Given a string, find the index of the first character that does not repeat. If all characters repeat, return -1.

    Approach

    To solve this problem, we can use a two-pass approach:

    1. Count Character Frequencies: Create a dictionary to store the frequency of each character in the string.
    2. Find the First Non-Repeating Character: Iterate through the string again and return the index of the first character with a frequency of 1.

    Code

    def first_non_repeating_char(s: str) -> int:
        """
        Find the index of the first non-repeating character in a string.
    
        Args:
        s (str): The input string.
    
        Returns:
        int: The index of the first non-repeating character. Returns -1 if all characters repeat.
        """
    
        # Create a dictionary to store character frequencies
        char_freq = {}
    
        # Count character frequencies
        for char in s:
            if char in char_freq:
                char_freq[char] += 1
            else:
                char_freq[char] = 1
    
        # Find the index of the first non-repeating character
        for i, char in enumerate(s):
            if char_freq[char] == 1:
                return i
    
        # If all characters repeat, return -1
        return -1
    
    
    # Example usage
    if __name__ == "__main__":
        print(first_non_repeating_char("leetcode"))  # Output: 0
        print(first_non_repeating_char("loveleetcode"))  # Output: 2
        print(first_non_repeating_char("aabbcc"))  # Output: -1
    

    Explanation

    • The first_non_repeating_char function takes a string s as input and returns the index of the first non-repeating character.
    • It first creates a dictionary char_freq to store the frequency of each character in the string.
    • The function then iterates through the string to count the frequency of each character.
    • In the second pass, it iterates through the string again and returns the index of the first character with a frequency of 1.
    • If no non-repeating character is found, the function returns -1.

    Time Complexity

    The time complexity of this solution is O(n), where n is the length of the input string, since we make two passes through the string.

    Space Complexity

    The space complexity is O(n) as well, as in the worst case, we might need to store the frequency of each character in the dictionary.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.