Last Updated: 22 Dec, 2020
First Unique Character in a String
Easy
Asked in companies
Given a string ‘STR’ consisting of lower case English letters, the task is to find the first non-repeating character in the string and return it. If it doesn’t exist, return ‘#’.
For example:
For the input string 'abcab', the first non-repeating character is ‘c’. As depicted the character ‘a’ repeats at index 3 and character ‘b’ repeats at index 4. Hence we return the character ‘c’ present at index 2.
Input Format:
The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.
The only line of each test case contains a single string ‘STR’ consisting of only lowercase English letters.
Output Format:
For each test case, print a single character representing the first non-repeating character in the given string.
The output for each test case is in a separate line.
Note:
You do not need to print anything; it has already been taken care of.
Constraints:
1 <= T <= 100
1 <= N <= 10 ^ 4
Where ‘T’ is the number of test cases, and ‘N’ is the length of the string.
Time Limit: 1 sec
Approaches
A character is said to be non-repeating if its frequency in the string is equal to 1. To find such characters, one needs to find the frequency of all characters in the string and check which character has a unit frequency. This task could be done efficiently using an array to map the character to their respective frequencies. We can simultaneously update the frequency of any character we come across in constant time. The maximum number of distinct characters in the ASCII system is 256. So the array has a maximum size of 256. Now read the string again, and the first character we find has a frequency as unity is the answer.
Below is the algorithm:
- Create an array that will map the character to their respective frequencies.
- Traverse the given string.
- Increase the count of the current character in the array.
- Now traverse the string again and check whether the current character has a frequency equal to 1.
- If the frequency is more than 1, continue the traversal.
- Else break the loop and update the answer.
- In the end, return the first unique character in the string.
Make an array count to store the index of the character if it appears only once, else it stores a negative value. So when it comes to finding the first non-repeating character, we just have to scan the array count instead of the string.
Below is the algorithm:
- Create an array count and initialize all characters by -1, i.e., all considered as absent.
- Traverse the given string, and the value of count[x] will be the index of x if x appears only once. Else, the value is going to be either -1 or -2, where -1 represents that this character is not encountered so far and -2 represents that the current character occurs more than once in the string.
- Now, traverse the array count and check if the i-th character occurs only once (count[i] has a positive value) and appears before the current result, then update the result.
- In the end, return the first unique character in the string.