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

One Response to algorithm to find first unrepeated character in a string

  1. Robin says:

    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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey