First Unique Character in a String
Difficulty: Easy
Asked in: Amazon, Microsoft
Understanding the problem
Problem description Given a string S, write a program to find the first non-repeating character in it and return its index.
Problem Note
- If a non-repeating character doesn’t exist, return -1.
- You may assume the string contains only lowercase letters.
Example 1
Input: S = "afteracademy"
Output: 1
Example 2
Input: S = "mindorks"
Output: 0
Example 3
Input: S = "abacdcd"
Output: -1
You should try to solve this problem here.
Solutions
We will be discussing two different approaches to solve this problem
- Brute Force Approach — Compare each pair of characters and find the first character which is not repeated.
- Using a hash map — Use a hash map to store the frequency of each character.
1. Brute Force Approach
To find the first non-repeating character, we may look for every pair of characters in the string. The first occurring character which does not have any pair will be the answer.
In case of no such characters, return -1.
Pseudo Code
int firstUniqueChar(string s) {
len = s.length()
for(i = 0 to i < len){
bool found = true
for(j = i+1 to j < len){
if(s[i] == s[j]){
found = false
break
}
}
if(found == true){
return i
}
}
return -1
}
Complexity Analysis
Time Complexity: O(n²)
Space Complexity: O(1)
Critical Ideas to Think
- Why we are using the found variable in the pseudo code?
- If we remove the break statement from the code, will the code work?
- Can you optimize the code to improve time complexity?
2. Using Hash Map
If you have read about hashmaps then, you would know that the lookup time of a key is constant. In this problem, we could use the hashmap to store the frequency of each character of the string and that could be done in a single pass of the string.
In another pass of the string, we may look for the first character with value in the map equal to 1.
Solution Step
- create one frequency map
- for each character c in the string, do
- if c is not in frequency, then insert it into frequency, and put value 1
- otherwise, increase the count in frequency
2. Scan the string and check if the value of the ith character in the map is 1 then return i. 3. Return -1, in case of the value of each character in the map, is greater than 1
Pseudo Code
int firstUniqChar(String s) {
Create a Hashmap freq
n = s.length()
// build hash map : character and how often it appears
for (int i = 0 to i < n) {
c = s[i]
freq[c] = freq[c] + 1
}
// find the index
for (int i = 0 to i < n) {
if (freq[s[i]] == 1)
return i
}
return -1
}
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
Critical Ideas to Think
- If we replace the freq map with an array of size 26 and use each index of the array as the (ASCII of that character) — 97, will that approach work? (97 is the ASCII of 'a')
Comparison of Different Approaches
Suggested Problems to Solve
- Sort Characters By Frequency
- Find the Nth occurrence of a character in the given String
- Find the last nonrepeating character in the string
- Find the first repeated character in a string
- Find the last index of a character in a string
- Find n-th character of the decrypted string
If you have any more approaches or you find an error/bug in the above solutions, please comment down below.
Happy Coding! Enjoy Algorithms!