Find the first non repeating character in string. Example: Input : ADBCGHIEFKJLADTVDERFSWVGHQWCNOPENSMSJWIERTFB Output: K
Please try solving this problem before jumping on the solution
Click to learn
Subscribe for more updates
Preparing for interviews? IDeserve team is here to help.
Create your profile
Create your profile, and here is what you will get:
1: Interview practice platform.
2: Once you are ready to take the interview, IDeserve team will help you get connected to the best job opportunities.
3: Personalized mentorship from IDeserve team once your interview process has started.
Creation of profile shouldn't take more than 2 minutes.
Solution 1: Naive Solution: Use 2 loops to check for every character whether it is non-repeating or not. Return the first such character found.
Linear Solution 1: Use a count array to store the count of every character. 1. Create a count array. 2. Initialize count of every element to 0. 3. Traverse the string once and increment the count of every element found in the string. 4. Traverse the string again and check for the first element for which count is set as 1. Return this element. 5. If not found, return null If string is large, traversing string again to find first element whose count is 1, is inefficient.
Linear Solution 2 (Optimized): Use index array for storing the index of the string elements. 1. Create an index array. 2. Initialize the index of all index array elements to -1. 3. Traverse the string once and for element of the string, check the value of index of that string element in index array. a. If index is -1, it is the first occurrence in the string. Set index[string.charAt(i)] = i b. Else, the element is repeating, set index[string.charAt(i)] = -2 4. Traverse the index array once, find the minimum value in the array which is non negative. If found, this is the index of the first non repeating character in the string. Else, return null.
Support us by whitelisting IDeserve in your ad-blocker.