Taro Logo

First Unique Character in a String

Easy
Amazon logo
Amazon
10 views
Topics:
StringsArrays

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

For example:

  • If s = "leetcode", the function should return 0 because 'l' at index 0 is the first non-repeating character.
  • If s = "loveleetcode", the function should return 2 because 'v' at index 2 is the first non-repeating character.
  • If s = "aabb", the function should return -1 because there are no non-repeating characters.

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of only lowercase English letters.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Can the input string `s` contain uppercase letters, lowercase letters, or other characters (e.g., numbers, symbols)?
  2. What is the maximum possible length of the input string `s`?
  3. If the string is empty, should I return -1 or is an empty string not a valid input?
  4. If there are multiple characters that appear only once, should I return the index of the first one encountered or is there some other criteria for choosing which index to return?
  5. Is it safe to assume that the string `s` will always be valid, or do I need to handle cases where the input is null or undefined?

Brute Force Solution

Approach

To find the first unique character in a string using a brute force method, we'll check each character individually. For every character, we'll compare it against all the other characters in the string to see if it appears more than once.

Here's how the algorithm would work step-by-step:

  1. Take the first character of the string.
  2. Compare that character to every other character in the string.
  3. If you find the same character appearing again, you know it's not unique, so stop comparing and move on to the next character.
  4. If you go through the entire string and never find the same character again, you've found the first unique character, and you're done.
  5. If the first character isn't unique, repeat this process with the second character, then the third, and so on, until you find a character that only appears once.
  6. If you reach the end of the string without finding any unique characters, it means there are no unique characters in the string.

Code Implementation

def first_unique_character(input_string):
    string_length = len(input_string)
    for first_index in range(string_length):
        is_unique = True

        # Assume the current character is unique until proven otherwise
        for second_index in range(string_length):

            # Skip comparing the character to itself
            if first_index == second_index:
                continue

            # If we find a matching character, it's not unique
            if input_string[first_index] == input_string[second_index]:
                is_unique = False
                break

        # We found a unique character
        if is_unique:
            return first_index

    # No unique character found
    return -1

Big(O) Analysis

Time Complexity
O(n²)The brute force approach iterates through the string of size n. For each character, it compares it with the rest of the string to check for duplicates. In the worst case, for the first character, we perform up to n-1 comparisons, for the second n-2, and so on. This nested comparison results in approximately n * (n-1) / 2 operations. Therefore, the time complexity is O(n²).
Space Complexity
O(1)The provided brute force solution iterates through the string using nested loops but does not utilize any auxiliary data structures to store character counts or other information. It only uses a few constant space variables for indexing and comparison. Thus, the space used remains constant regardless of the input string's length (N). Therefore, the space complexity is O(1).

Optimal Solution

Approach

The best way to find the first unique character involves counting how many times each character appears. We can then go through the string one time to find the first character with a count of one.

Here's how the algorithm would work step-by-step:

  1. First, we need to figure out how many times each character shows up in the string.
  2. We can go through the entire string and keep track of the count for each character.
  3. Once we have the counts, we can go through the string again, but this time checking each character's count.
  4. The first character we find that has a count of one is our answer.
  5. If we get to the end without finding a character that only appears once, that means there are no unique characters.

Code Implementation

def first_unique_character(input_string):
    character_counts = {}

    # Count occurrences of each character
    for character in input_string:
        if character in character_counts:
            character_counts[character] += 1
        else:
            character_counts[character] = 1

    # Find the first unique character
    for index, character in enumerate(input_string):
        #Check if this is a unique character
        if character_counts[character] == 1:
            return index

    #If no unique character, return -1
    return -1

Big(O) Analysis

Time Complexity
O(n)The algorithm iterates through the string once to count character frequencies; this takes O(n) time where n is the length of the string. Afterwards, it iterates through the string again to find the first character with a frequency of one, also taking O(n) time. Because we perform two iterations through the string in sequence, the time complexity is O(n) + O(n), which simplifies to O(n).
Space Complexity
O(1)The dominant factor in auxiliary space is the character count. Since we are dealing with characters, the number of possible characters is limited by the character set used (e.g., ASCII or Unicode). Even in the case of Unicode, the character set size is constant. Therefore, the space required to store the counts for each character is independent of the input string's length (N), and the space used remains constant and limited by the size of the character set, not the length of the string. This constant space usage approximates to O(1).

Edge Cases

CaseHow to Handle
Empty stringReturn -1 immediately since there are no characters to check.
Null stringThrow an IllegalArgumentException or return -1 depending on the specification.
String with only one characterReturn 0 as it is the first and only character and therefore unique.
String with all identical charactersReturn -1 as there are no unique characters.
String with a very long length (close to maximum string size)The solution should use an efficient data structure like a hash map to avoid quadratic time complexity.
String with only special characters or non-ASCII charactersThe solution should correctly handle any character including Unicode.
String where the first unique character is near the endThe solution should iterate through the entire string to find the first unique character.
String containing mixed case characters (e.g., 'a' and 'A')Consider whether case sensitivity is required and handle by converting to lowercase/uppercase or by treating them as distinct characters.