Jobs

Interviews

Discussions

First Unique Character in a String

Easy

Goldman Sachs

3 views

Topics:

Strings

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

Example 1:

Input: s = "leetcode"

Output: 0

Explanation:

The character 'l' at index 0 is the first character that does not occur at any other index.

Example 2:

Input: s = "loveleetcode"

Output: 2

Example 3:

Input: s = "aabb"

Output: -1

Constraints:

1 <= s.length <= 10⁵
s consists of only lowercase English letters.

First Unique Character in a String

Easy

Goldman Sachs

3 views

Topics:

Strings

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

Example 1:

Input: s = "leetcode"

Output: 0

Explanation:

The character 'l' at index 0 is the first character that does not occur at any other index.

Example 2:

Input: s = "loveleetcode"

Output: 2

Example 3:

Input: s = "aabb"

Output: -1

Constraints:

1 <= s.length <= 10⁵
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:

Is the input string `s` case-sensitive, or should I treat uppercase and lowercase letters as the same?
Can the input string `s` be empty or null?
What characters can the string `s` contain? (e.g., only ASCII characters, Unicode characters, etc.)
If multiple characters appear only once, should I return the index of the first one encountered from left to right?
Besides returning -1 when there is no unique character, are there any other specific error conditions I should handle or exceptions I should throw?

Brute Force Solution

Approach

The brute force approach to finding the first unique character involves checking each character in the string against every other character. We're essentially trying every possible comparison to see if a character appears only once. If it does, we've found our answer.

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

Take the very first character in the string.
Compare it with every other character in the string.
If you find the same character anywhere else in the string, you know the first character is not unique, and you can move on.
If you go through the entire string and never find a match for the first character, that means it appears only once, and it's your answer.
If the first character wasn't unique, move on to the second character in the string and repeat the process: compare it to every other character.
Continue this process, character by character, until you find one that appears only once.
If you get to the end of the string without finding any unique characters, then there are no unique characters in the string.

Code Implementation

def find_first_unique_character(input_string):
    string_length = len(input_string)

    for current_index in range(string_length):
        is_unique = True

        # Compare the current character to the rest of the string

        for comparison_index in range(string_length):
            # Skip comparing the character to itself
            if current_index == comparison_index:
                continue

            # If we find a matching character, it is not unique

            if input_string[current_index] == input_string[comparison_index]:
                is_unique = False
                break

        # If after comparing to all characters the current character remains unique, we return

        if is_unique:
            return current_index

    # If no unique character found, return -1

    return -1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates through each of the n characters in the string. For each character in the outer loop, the inner loop compares it with every other character in the string to check for uniqueness. This inner loop also has a worst-case time complexity of O(n). Therefore, in the worst case, we perform n iterations of an O(n) operation, resulting in a total of approximately n * n comparisons. This means the time complexity is O(n²).

Space Complexity

O(1) – The described brute force approach iterates through the string using index variables to compare characters. No auxiliary data structures, like arrays, hash maps, or stacks, are allocated to store intermediate results or track seen characters. The algorithm only uses a constant amount of extra space for index variables 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 in a string is to first count how many times each character appears. Then, go back through the string and find the first character that only appeared once.

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

Go through the string and keep track of the number of times each character appears.
After you have the count of each character, go back to the start of the string.
For each character, check its count. If a character appeared only once, then it is the first unique character.
If you find a character that appears only once, stop and return it.
If you go through the whole string and don't find any character that appears only once, then there are no unique characters, and return an indication of that (for example an empty character).

Code Implementation

def find_first_unique_character(input_string):
    character_counts = {}

    for character in input_string:
        character_counts[character] = character_counts.get(character, 0) + 1

    # Iterate through the string to find the first unique character.
    for character in input_string:
        # Check if the character count is equal to 1
        if character_counts[character] == 1:
            return character

    # If no unique character is found, return an empty string.
    return ''

Try it yourself on LeetCode

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. It then iterates through the string again to find the first unique character, which also takes O(n) time. Because these operations are performed sequentially, the overall time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(1) – The described solution uses a character count. Since we are dealing with characters, and the character set size is fixed (e.g., ASCII or Unicode), the space required to store the character counts is constant and does not depend on the input string's length, N. Thus, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input string	Return -1 immediately as there are no characters to evaluate.
String with a single character	Return 0, as the first character is trivially unique.
String with all identical characters	The solution should correctly identify that no character is unique and return -1 after iterating through the entire string.
Very long string (approaching maximum string length)	Ensure the solution's time and space complexity are acceptable; hash map or character count array approaches are generally efficient.
String with only repeating characters at the beginning and a single unique character at the end	The algorithm should correctly identify the unique character at the end, as it will be encountered last.
String containing non-ASCII characters (Unicode)	Ensure the character counting mechanism (e.g., hash map) can handle the full range of Unicode characters correctly.
String with multiple unique characters; return the first one	The solution needs to stop at the first encountered unique character and return its index, not continue searching.
String with mixed case letters (e.g., 'a' and 'A')	The problem did not specify case sensitivity, so either treat them as unique or normalize the string to lower/upper case before processing based on clarification with the interviewer.

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:

Is the input string `s` case-sensitive, or should I treat uppercase and lowercase letters as the same?
Can the input string `s` be empty or null?
What characters can the string `s` contain? (e.g., only ASCII characters, Unicode characters, etc.)
If multiple characters appear only once, should I return the index of the first one encountered from left to right?
Besides returning -1 when there is no unique character, are there any other specific error conditions I should handle or exceptions I should throw?

Brute Force Solution

Approach

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

Take the very first character in the string.
Compare it with every other character in the string.
If you find the same character anywhere else in the string, you know the first character is not unique, and you can move on.
If you go through the entire string and never find a match for the first character, that means it appears only once, and it's your answer.
If the first character wasn't unique, move on to the second character in the string and repeat the process: compare it to every other character.
Continue this process, character by character, until you find one that appears only once.
If you get to the end of the string without finding any unique characters, then there are no unique characters in the string.

Code Implementation

def find_first_unique_character(input_string):
    string_length = len(input_string)

    for current_index in range(string_length):
        is_unique = True

        # Compare the current character to the rest of the string

        for comparison_index in range(string_length):
            # Skip comparing the character to itself
            if current_index == comparison_index:
                continue

            # If we find a matching character, it is not unique

            if input_string[current_index] == input_string[comparison_index]:
                is_unique = False
                break

        # If after comparing to all characters the current character remains unique, we return

        if is_unique:
            return current_index

    # If no unique character found, return -1

    return -1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Go through the string and keep track of the number of times each character appears.
After you have the count of each character, go back to the start of the string.
For each character, check its count. If a character appeared only once, then it is the first unique character.
If you find a character that appears only once, stop and return it.
If you go through the whole string and don't find any character that appears only once, then there are no unique characters, and return an indication of that (for example an empty character).

Code Implementation

def find_first_unique_character(input_string):
    character_counts = {}

    for character in input_string:
        character_counts[character] = character_counts.get(character, 0) + 1

    # Iterate through the string to find the first unique character.
    for character in input_string:
        # Check if the character count is equal to 1
        if character_counts[character] == 1:
            return character

    # If no unique character is found, return an empty string.
    return ''

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return -1 immediately as there are no characters to evaluate.
String with a single character	Return 0, as the first character is trivially unique.
String with all identical characters	The solution should correctly identify that no character is unique and return -1 after iterating through the entire string.
Very long string (approaching maximum string length)	Ensure the solution's time and space complexity are acceptable; hash map or character count array approaches are generally efficient.
String with only repeating characters at the beginning and a single unique character at the end	The algorithm should correctly identify the unique character at the end, as it will be encountered last.
String containing non-ASCII characters (Unicode)	Ensure the character counting mechanism (e.g., hash map) can handle the full range of Unicode characters correctly.
String with multiple unique characters; return the first one	The solution needs to stop at the first encountered unique character and return its index, not continue searching.
String with mixed case letters (e.g., 'a' and 'A')	The problem did not specify case sensitivity, so either treat them as unique or normalize the string to lower/upper case before processing based on clarification with the interviewer.