Amazon Coding Interview Question - firstNonRepeatingCharacter | Example Code | InterviewDOT
Channel: Interview DOT
Date: 2020-03-11

Click here - https://www.youtube.com/channel/UCd0U_xlQxdZynq09knDszXA?sub_confirmation=1 to get notifications.

Tamil Amazon Coding Interview Question - firstNonRepeatingCharacter | Example Code | InterviewDOT

Given a string, find its first non-repeating character
Given a string, find the first non-repeating character in it. For example, if the input string is “GeeksforGeeks”, then output should be ‘f’ and if input string is “GeeksQuiz”, then output should be ‘G’.

First step : Scan String and store count of each character in HashMap. Second Step : traverse String and get count for each character from Map. Since we are going through String from first to last character, when count for any character is 1, we break, it's the first non repeated character.

3 ways to Find First Non Repeated Character in a String - Java Programming Problem

Here is the full code sample of finding first duplicate character in a given String. This program has three method to find first non-repeated character. Each uses their own algorithm to do this programming task. First algorithm is implemented in getFirstNonRepeatedChar(String str) method. It first gets character array from given String and loop through it to build a hash table with character as key and their count as value. In next step, It loop through LinkedHashMap to find an entry with value 1, that's your first non-repeated character, because LinkedHashMap maintains insertion order, and we iterate through character array from beginning to end. Bad part is it requires two iteration, first one is proportional to number of character in String, and second is proportional to number of duplicate characters in String. In worst case, where String contains non-repeated character at end, it will take 2*N time to solve this problem.

Second way to find first non-repeated or unique character is coded on firstNonRepeatingChar(String word) ,this solution finds first non repeated character in a String in just one pass. It applies classical space-time trade-off technique. It uses two storage to cut down one iteration, standard space vs time trade-off. Since we store repeated and non-repeated characters separately, at the end of iteration, first element from List is our first non repeated character from String. This one is slightly better than previous one, though it's your choice to return null or empty string if there is no non-repeated character in the String. Third way to solve this programming question is implemented in  firstNonRepeatedCharacter(String word) method. It's very similar to first one except the fact that instead of LinkedHashMap, we have used HashMap. Since later doesn't guarantee any order, we have to rely on original String for finding first non repeated character. Here is the algorithm of this third solution. First step : Scan String and store count of each character in HashMap. Second Step : traverse String and get count for each character from Map. Since we are going through String from first to last character, when count for any character is 1, we break, it's the first non repeated character. Here order is achieved by going through String again.