# algorithm to find first unrepeated character in a string

April 19, 2013 1 Comment

We can do it in two different ways

- Algorithm with O(2n) time complexity and O(1) space complexity
- Algorithm with O(2n) time complexity and O(n) space complexity

**Algorithm with O(2n) time complexity and O(1) space complexity**

Here we take a fixed size (256 in which all characters small and caps fall into) integer array and we scan the string two times

- First scan we increment the counter in integer array for every character that appears in string
- In second scan, we look for counter value 1 which gives the first unrepeated character in string

**Note:** Here space complexity is O(1) because the int array size is always constant irrespective of the string we pass

public static char firtUnrepeatedCharInString(char[] s) { char result = '\0'; int[] counts = new int[256]; for (char c : s) { counts[c]++; } for (int i = 0; i < s.length; i++) { if (counts[s[i]] == 1) { result = s[i]; break; } } return result; }

**Algorithm with O(2n) time complexity and O(n) space complexity**

Here we take hashmap and we scan the string two times

- First scan we insert every character that appears in string as key and its number of appearances as value in hashmap
- In second, scan we look for key whose value is 1 which gives the first unrepeated character in string

public static char firtUnrepeatedCharInString(char[] s) { char result = '\0'; HashMap<Character, Integer> hm = new HashMap<Character, Integer>(); for (char c : s) { Object o = hm.get(c); if(o == null) { hm.put(c, 1); } else { int ctr = hm.get(c); hm.put(c, ++ctr); } } for (char c : s) { int ctr = hm.get(c); if(ctr == 1) { result = c; break; } } return result; }

For approach 2:

Since the hash map can’t 100% guarantee the order of elements (here the approach is assuming the order of insertion is preserved by HMap), how can we be certain of the “first” un-repeated character ? It may very well be the second or third un-repeated character as well?