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:
s = "leetcode"
, the function should return 0
because 'l'
at index 0 is the first non-repeating character.s = "loveleetcode"
, the function should return 2
because 'v'
at index 2 is the first non-repeating character.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.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:
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:
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
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:
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
Case | How to Handle |
---|---|
Empty string | Return -1 immediately since there are no characters to check. |
Null string | Throw an IllegalArgumentException or return -1 depending on the specification. |
String with only one character | Return 0 as it is the first and only character and therefore unique. |
String with all identical characters | Return -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 characters | The solution should correctly handle any character including Unicode. |
String where the first unique character is near the end | The 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. |