Last Updated: 1 Dec, 2020
First non repeating character
Easy
Asked in companies
Ninja is now bored with numbers and is now playing with characters but hates when he gets repeated characters. Ninja is provided a string, and he wants to return the first unique character in the string.The string will contain characters only from the English alphabet set, i.e., ('A' - 'Z') and ('a' - 'z'). If there is no non-repeating character, print the first character of the string. If there is no non-repeating character, return the first character of the string.
Input Format:
The first line contains a single integer T representing the number of test cases.
The first and the only line of each test case will contain the input string.
Output Format:
For each test case, print a character denoting the first non-repeating character in the input string.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= Length of Input String <= 10^4
Time Limit: 1 sec
Approaches
We will traverse the whole array and check if that element previously occurred or not.
The steps are as follows:
- We will iterate over all the elements of the array, i.e., i = 0 to i = N - 1:
- We will iterate over all the elements of the array excluding the present element, i.e., j = 0 to i = N - 1:
- If we get that for no j, S[i] equals S[j], then we return S[i].
- We will iterate over all the elements of the array excluding the present element, i.e., j = 0 to i = N - 1:
- We will return the first character of the string if the loop completes and no answer is returned.
We will traverse the whole array and keep a count of the frequency of each element. If the frequency is one, then we return that element. If the occurrence of all the elements is more than one, then we simply return the first character of the string.
The steps are as follows:
- We initialize a hash map ‘frequencyOfCharacters’ to store the frequency of each element.
- We will iterate over the length of the string ‘S’, i.e., i = 0 to i = N - 1:
- We will store the frequency of a character at position i in ‘frequencyOfCharacters’.
- If the element already exists in ‘frequencyOfCharacters’, then increment ‘frequencyOfCharacters’ for that character.
- We will iterate over the length of the string, i.e., i = 0 to i = N - 1:
- If frequencyOfCharacters[S[i]] is 1 then we return the value of S[i] as the final answer.
- We will return the first character of the string as the final answer.