Given a string s, find the first non-repeating character in it and return its index . If it does not exist,
return -1.
Problem Statement
The problem is to find the index of the first non-repeating character in a given string s. If there is no such character, the
function should return -1.
For example, if the input string is "leetcode", the first non-repeating character is 'l', and the function should return 0. If
the input string is "loveleetcode", the first non-repeating character is 'v', and the function should return 2.
Examples
Example 1:
Input: s = "leetcode"
Output: 0
Example 2:
Input: s = "loveleetcode"
Output: 2
Example 3:
Input: s = "aabb"
Output: -1
Clarifying Questions
Can you give me an example of input and expected output for this problem?
Are the characters in the string case-sensitive?
Can the string contain special characters or only alphabets?
Is there a constraint on the size of the input string?
Can I assume that the input string is non-empty?
Solutions
Here are a few different approaches you could take to solve this problem:
Brute Force
Hash Map Approach
Two-Pass Hash Map Approach
Queue Approach
Linked List
Brute Force Approach:
One way to solve this problem is by iterating over the string and comparing each character with every other character in the string. This approach
would have a time complexity of O(n^2), where n is the length of the input string.
Algorithm:
Iterate over each character in the string.
For each character, iterate over the entire string again to check if it's a non-repeating character.
If the character is non-repeating, return its index.
If there are no non-repeating characters, return -1.
public int FirstUniqChar(string s) {
// Iterate over each character in the string.
for (int i = 0; i < s.Length; i++) {
bool isDuplicate = false;
// For each character, iterate over the entire string again to check if it's a non-repeating character.
for (int j = 0; j < s.Length; j++) {
if (i != j && s[i] == s[j]) {
// If the character is repeated, mark it as a duplicate and break out of the inner loop.
isDuplicate = true;
break;
}
}
// If the character is not a duplicate, return its index.
if (!isDuplicate) {
return i;
}
}
// If there are no non-repeating characters, return -1.
return -1;
}
def first_uniq_char(s: str) -> int:
# Iterate over each character in the string.
for i in range(len(s)):
isDuplicate = False
# For each character, iterate over the entire string again to check if it's a non-repeating character.
for j in range(len(s)):
if i != j and s[i] == s[j]:
# If the character is repeated, mark it as a duplicate and break out of the inner loop.
isDuplicate = True
break
# If the character is not a duplicate, return its index.
if not isDuplicate:
return i
# If there are no non-repeating characters, return -1.
return -1
public static int firstUniqChar(String s) {
// Iterate over each character in the string.
for (int i = 0; i < s.length(); i++) {
boolean isDuplicate = false;
// For each character, iterate over the entire string again to check if it's a non-repeating character.
for (int j = 0; j < s.length(); j++) {
if (i != j && s.charAt(i) == s.charAt(j)) {
// If the character is repeated, mark it as a duplicate and break out of the inner loop.
isDuplicate = true;
break;
}
}
// If the character is not a duplicate, return its index.
if (!isDuplicate) {
return i;
}
}
// If there are no non-repeating characters, return -1.
return -1;
}
int FirstUniqChar(string s) {
// Iterate over each character in the string.
for (int i = 0; i < s.length(); i++) {
bool isDuplicate = false;
// For each character, iterate over the entire string again to check if it's a non-repeating character.
for (int j = 0; j < s.length(); j++) {
if (i != j && s[i] == s[j]) {
// If the character is repeated, mark it as a duplicate and break out of the inner loop.
isDuplicate = true;
break;
}
}
// If the character is not a duplicate, return its index.
if (!isDuplicate) {
return i;
}
}
// If there are no non-repeating characters, return -1.
return -1;
}
Time and Space Complexity:
The Brute Force approach has a time complexity of O(n^2) since we are iterating over the string twice and checking each character against all the
other characters. It has a space complexity of O(1) since we are not using any extra data structures.
Hash Map Approach:
Another approach is to use a hash map to store the frequency of each character in the string. After building the hash map, we can then iterate
over the string and check for the first character with a frequency of 1. This approach would have a time complexity of O(n), where n is the length
of the input string.
Algorithm:
Create an empty hash map to store the frequency of each character.
Iterate over each character in the string and update its frequency in the hash map.
Iterate over the string again and check if the frequency of each character is 1.
If the frequency is 1, return the index of that character.
If there are no non-repeating characters, return -1.
public int FirstUniqChar(string s) {
// Create an empty hash map to store the frequency of each character.
Dictionary<char, int> charFreq = new Dictionary<char, int>();
// Iterate over each character in the string and update its frequency in the hash map.
foreach (char c in s) {
if (charFreq.ContainsKey(c)) {
charFreq[c]++;
} else {
charFreq[c] = 1;
}
}
// Iterate over the string again and check if the frequency of each character is 1.
for (int i = 0; i < s.Length; i++) {
if (charFreq[s[i]] == 1) {
// If the frequency is 1, return the index of that character.
return i;
}
}
// If there are no non-repeating characters, return -1.
return -1;
}
def first_uniq_char(s: str) -> int:
# Create an empty dictionary to store the frequency of each character.
char_freq = {}
# Iterate over each character in the string and update its frequency in the dictionary.
for c in s:
if c in char_freq:
char_freq[c] += 1
else:
char_freq[c] = 1
# Iterate over the string again and check if the frequency of each character is 1.
for i in range(len(s)):
if char_freq[s[i]] == 1:
# If the frequency is 1, return the index of that character.
return i
# If there are no non-repeating characters, return -1.
return -1
public int firstUniqChar(String s) {
// Create an empty hash map to store the frequency of each character.
Map<Character, Integer> charFreq = new HashMap<>();
// Iterate over each character in the string and update its frequency in the hash map.
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (charFreq.containsKey(c)) {
charFreq.put(c, charFreq.get(c) + 1);
} else {
charFreq.put(c, 1);
}
}
// Iterate over the string again and check if the frequency of each character is 1.
for (int i = 0; i < s.length(); i++) {
if (charFreq.get(s.charAt(i)) == 1) {
// If the frequency is 1, return the index of that character.
return i;
}
}
// If there are no non-repeating characters, return -1.
return -1;
}
int firstUniqChar(string s) {
// Create an empty hash map to store the frequency of each character.
unordered_map<char, int> charFreq;
// Iterate over each character in the string and update its frequency in the hash map.
for (char c : s) {
if (charFreq.find(c) != charFreq.end()) {
charFreq[c]++;
} else {
charFreq[c] = 1;
}
}
// Iterate over the string again and check if the frequency of each character is 1.
for (int i = 0; i < s.length(); i++) {
if (charFreq[s[i]] == 1) {
// If the frequency is 1, return the index of that character.
return i;
}
}
// If there are no non-repeating characters, return -1.
return -1;
}
Time and Space complexity:
The Hash Map approach has a time complexity of O(n) since we are iterating over the string only once and performing constant-time operations on
the hash map. It has a space complexity of O(k) where k is the size of the character set, since we are using a hash map to store the frequency of
each character.
Queue Approach:
We can use a queue to store the characters and their frequency in the order they appear in the string. After building the queue, we can then
iterate over the queue and check for the first character with a frequency of 1. This approach would have a time complexity of O(n), where n is the
length of the input string.
Algorithm:
Create an empty queue to store the characters and their frequency in the order they appear in the string.
Iterate over each character in the string and update its frequency in the queue.
Iterate over the queue and check if the frequency of each character is 1.
If the frequency is 1, return the index of that character.
If there are no non-repeating characters, return -1.
public int FirstUniqChar(string s) {
// Create a hash map to store the frequency of each character and a queue to store non-repeating characters.
Dictionary<char, int> charFreq = new Dictionary<char, int>();
Queue<int> nonRepeatingChars = new Queue<int>();
// Iterate over each character in the string and update its frequency in the hash map.
for (int i = 0; i < s.Length; i++) {
char c = s[i];
if (charFreq.ContainsKey(c)) {
charFreq[c]++;
} else {
charFreq[c] = 1;
nonRepeatingChars.Enqueue(i);
}
}
// Dequeue the index of the first non-repeating character from the queue and return it.
while (nonRepeatingChars.Count > 0) {
int index = nonRepeatingChars.Dequeue();
if (charFreq[s[index]] == 1) {
return index;
}
}
// If there are no non-repeating characters, return -1.
return -1;
}
def first_uniq_char(s: str) -> int:
# Create a dictionary to store the frequency of each character and a queue to store non-repeating characters.
char_freq = {}
non_repeating_chars = []
# Iterate over each character in the string and update its frequency in the dictionary.
for i in range(len(s)):
c = s[i]
if c in char_freq:
char_freq[c] += 1
else:
char_freq[c] = 1
non_repeating_chars.append(i)
# Dequeue the index of the first non-repeating character from the queue and return it.
while non_repeating_chars:
index = non_repeating_chars.pop(0)
if char_freq[s[index]] == 1:
return index
# If there are no non-repeating characters, return -1.
return -1
public int firstUniqChar(String s) {
// Create a hash map to store the frequency of each character and a queue to store non-repeating characters.
Map<Character, Integer> charFreq = new HashMap<>();
Queue<Integer> nonRepeatingChars = new LinkedList<>();
// Iterate over each character in the string and update its frequency in the hash map.
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (charFreq.containsKey(c)) {
charFreq.put(c, charFreq.get(c) + 1);
} else {
charFreq.put(c, 1);
nonRepeatingChars.add(i);
}
}
// Dequeue the index of the first non-repeating character from the queue and return it.
while (!nonRepeatingChars.isEmpty()) {
int index = nonRepeatingChars.remove();
if (charFreq.get(s.charAt(index)) == 1) {
return index;
}
}
// If there are no non-repeating characters, return -1.
return -1;
}
int firstUniqChar(string s) {
// Create an unordered_map to store the frequency of each character and a queue to store non-repeating characters.
unordered_map<char, int> charFreq;
queue<int> nonRepeatingChars;
// Iterate over each character in the string and update its frequency in the unordered_map.
for (int i = 0; i < s.length(); i++) {
char c = s[i];
if (charFreq.count(c)) {
charFreq[c]++;
} else {
charFreq[c] = 1;
nonRepeatingChars.push(i);
}
}
// Dequeue the index of the first non-repeating character from the queue and return it.
while (!nonRepeatingChars.empty()) {
int index = nonRepeatingChars.front();
nonRepeatingChars.pop();
if (charFreq[s[index]] == 1) {
return index;
}
}
// If there are no non-repeating characters, return -1.
return -1;
}
Time and Space Complexity:
The Queue approach has a time complexity of O(n) since we are iterating over the string only twice (once to update the hash map and the queue, and
once to dequeue the non-repeating characters) and performing constant-time operations on the hash map and the queue. It has a space complexity of
O(k) where k is the size of the character set, since we are using a hash map to store the frequency of each character and a queue to store the
indices of non-repeating characters.
Note that this approach uses a hash map to keep track of the frequency of each character and a queue to store the indices of non-repeating
characters. We iterate over the string once to update the hash map and the queue. Then, we dequeue the indices from the queue and return the first
one whose frequency is 1. This approach has a time complexity of O(n) since we are iterating over the string only twice. It is recommended for
solving the problem for large strings when using a queue.
Linked List Approach:
Algorithm:
Create a doubly linked list and initialize two pointers: head and tail.
Iterate over the input string character by character.
For each character:
Check if the character is already present in the linked list. If it is, remove the node from the list since it is no longer a non-repeating
character.
If the character is not present in the list, create a new node for it and append it to the tail of the linked list.
After iterating over the entire string, the head of the linked list will point to the first non-repeating character in the string. If the head
is NULL, then there are no non-repeating characters in the string.
Return the index of the first non-repeating character by iterating over the string again and comparing each character with the character at the
head node of the linked list.
public int FirstUniqChar(string s) {
// Create a hash map to store the frequency of each character and a linked list to store non-repeating characters.
Dictionary<char, int> charFreq = new Dictionary<char, int>();
LinkedList<int> nonRepeatingChars = new LinkedList<int>();
LinkedListNode<int>[] nodes = new LinkedListNode<int>[26];
// Iterate over each character in the string and update its frequency in the hash map.
for (int i = 0; i < s.Length; i++) {
char c = s[i];
if (charFreq.ContainsKey(c)) {
charFreq[c]++;
if (nodes[c - 'a'] != null) {
nonRepeatingChars.Remove(nodes[c - 'a']);
nodes[c - 'a'] = null;
}
} else {
charFreq[c] = 1;
LinkedListNode<int> node = nonRepeatingChars.AddLast(i);
nodes[c - 'a'] = node;
}
}
// Check the first node in the linked list to see if it has a frequency of 1.
if (nonRepeatingChars.First != null && charFreq[s[nonRepeatingChars.First.Value]] == 1) {
return nonRepeatingChars.First.Value;
}
// If there are no non-repeating characters, return -1.
return -1;
}
def firstUniqChar(s: str) -> int:
# Create a dictionary to store the frequency of each character and a queue to store non-repeating characters.
charFreq = {}
nonRepeatingChars = []
# Iterate over each character in the string and update its frequency in the dictionary.
for i in range(len(s)):
c = s[i]
if c in charFreq:
charFreq[c] += 1
else:
charFreq[c] = 1
nonRepeatingChars.append(i)
# Dequeue the index of the first non-repeating character from the queue and return it.
while len(nonRepeatingChars) > 0:
index = nonRepeatingChars.pop(0)
if charFreq[s[index]] == 1:
return index
# If there are no non-repeating characters, return -1.
return -1
public int firstUniqChar(String s) {
// Create a hash map to store the frequency of each character and a queue to store non-repeating characters.
Map<Character, Integer> charFreq = new HashMap<>();
Queue<Integer> nonRepeatingChars = new LinkedList<>();
// Iterate over each character in the string and update its frequency in the hash map.
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (charFreq.containsKey(c)) {
charFreq.put(c, charFreq.get(c) + 1);
} else {
charFreq.put(c, 1);
nonRepeatingChars.offer(i);
}
}
// Dequeue the index of the first non-repeating character from the queue and return it.
while (!nonRepeatingChars.isEmpty()) {
int index = nonRepeatingChars.poll();
if (charFreq.get(s.charAt(index)) == 1) {
return index;
}
}
// If there are no non-repeating characters, return -1.
return -1;
}
int FirstUniqChar(string s) {
// Create a hash map to store the frequency of each character and a queue to store non-repeating characters.
unordered_map<char, int> charFreq;
queue<int> nonRepeatingChars;
// Iterate over each character in the string and update its frequency in the hash map.
for (int i = 0; i < s.length(); i++) {
char c = s[i];
if (charFreq.count(c)) { // if the character exists in the hash map
charFreq[c]++; // increase the frequency count
} else { // if the character is not in the hash map
charFreq[c] = 1; // add it with a frequency count of 1
nonRepeatingChars.push(i); // and add its index to the queue
}
}
// Dequeue the index of the first non-repeating character from the queue and return it.
while (!nonRepeatingChars.empty()) { // while the queue is not empty
int index = nonRepeatingChars.front(); // get the index of the first non-repeating character
nonRepeatingChars.pop(); // remove it from the queue
if (charFreq[s[index]] == 1) { // if its frequency count is 1
return index; // return its index
}
}
// If there are no non-repeating characters, return -1.
return -1;
}
Note: In the C++ code, we use
unordered_map instead of Dictionary and queue instead of Queue. We also use
length() instead of Length to get the length of the string. The rest of the code follows the same logic and structure
as the original code.
Time and Space Complexity:
The Linked List approach has a time complexity of O(n) since we are iterating over the string only once and performing constant-time operations on
the hash map and the linked list. It has a space complexity of O(k) where k is the size of the character set, since we are using a hash map to
store the frequency of each character and a linked list to store the indices of non-repeating characters.
In terms of time complexity, the Queue and Linked List approaches are the most efficient since they have a time complexity of O(n). However, the
space complexity of both of these approaches is O(k), where k is the size of the character set. So if the character set is very large, then
these approaches might not be the best choice in terms of space efficiency.
The Hash Map and Two-Pass Hash Map approaches have a space complexity of O(k), which is better than the Queue and Linked List approaches. They
also have a time complexity of O(n), which is the same as the Queue and Linked List approaches. So, if space efficiency is a concern and the
character set is not very large, then these approaches might be the best choice.
The Brute Force approach is the least efficient in terms of time complexity, with a time complexity of O(n^2), and does not use any extra space.
However, it is only suitable for small inputs where the performance is not a major concern.
Overall, the Hash Map and Two-Pass Hash Map approaches are commonly used and provide a good balance between time and space efficiency, making
them a popular choice for solving this problem.
