algorithm to find first unrepeated character in a string

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;
	}