One of the interview question is “How will you find first non repeating character in String.”
For example:
If input string is “analogy”, then program should return ‘n’
If input string is “easiest”, then program should return ‘a’
If input string is “analogy”, then program should return ‘n’
If input string is “easiest”, then program should return ‘a’
First approach:
We will use LinkedHashMap to find first non repeating character in String.
Algorithm:
- Get character while looping over String
- Put this character in LinkedHashMap with count. If character is already there, increase count by 1.
- Get count from LinkedHashMap while iterating. If count is 1,return that character as LinkedHashMap maintains insertion order.
Program:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
package org.arpit.java2blog.algo; import java.text.*; import java.util.*; import java.util.Map.Entry; public class GetFirstNonRepeatingCharacterMain { public static void main(String[] args) { System.out .println("First non repeated character for String analogy is : " + getNonRepeatedCharacter("analogy")); System.out .println("First non repeated character for String easiest is : " + getNonRepeatedCharacter("easiest")); } public static Character getNonRepeatedCharacter(String str) { Map<Character, Integer> countCharacters = new LinkedHashMap<Character, Integer>(); for (int i = 0; i < str.length() - 1; i++) { Character c = str.charAt(i); if (!countCharacters.containsKey(c)) { countCharacters.put(c, 1); } else { countCharacters.put(c, countCharacters.get(c) + 1); } } // As LinkedHashMap maintains insertion order, first character with // count 1 should return first non repeated character for (Entry<Character, Integer> e : countCharacters.entrySet()) { if (e.getValue() == 1) return e.getKey(); } return null; } } |
When you run above program, you will get following output:
|
1 2 3 4 |
First non repeated character for String analogy is : n First non repeated character for String easiest is : a |
Second Approach:
Algorithm:
- Iterate through each character of string.
- If lastIndexOf and indexOf return same value, then it is first non repeating character in the String.
Program:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
package org.arpit.java2blog.algo public class GetFirstNonRepeatingCharacterMain { public static void main(String[] args) { System.out.println("First non repeated character for String analogy is : "+getNonRepeatedCharacter("analogy")); System.out.println("First non repeated character for String easiest is : "+getNonRepeatedCharacter("easiest")); } public static Character getNonRepeatedCharacter(String str) { char charaaray[]=str.toCharArray(); for (int i=0; i<str.length();i++) { if (str.lastIndexOf(charaaray[i]) == str.indexOf(charaaray[i])) return charaaray[i]; } return null; } } |
When you run above program, you will get following output:
|
1 2 3 4 |
First non repeated character for String analogy is : n First non repeated character for String easiest is : a |
Please go through Common java interview Programs for more such programs.
