CODEWITHSUNDEEP
javastringalgorithmdata-structures
DavidB
DavidB

Reputation: 23

First non-repeating character in a stream

My answer to this question is as follows, but I want to know if I can use this code and what will be the complexity:

import java.util.LinkedHashMap;
import java.util.Map.Entry;

public class FirstNonRepeatingCharacterinAString {

    private char firstNonRepeatingCharacter(String str) {       
        LinkedHashMap<Character, Integer> hash =
                new LinkedHashMap<Character, Integer>();

        for(int i = 0 ; i< str.length() ; i++)
        {
            if(hash.get(str.charAt(i))==null)
                hash.put(str.charAt(i), 1);
            else
                hash.put(str.charAt(i), hash.get(str.charAt(i))+1);
        }

        System.out.println(hash.toString());

        for(Entry<Character, Integer> c : hash.entrySet())
        {
            if(c.getValue() == 1)
                return c.getKey();
        }

        return 0 ;
    }

    public static void main(String args[])
    {
        String str = "geeksforgeeks";
        FirstNonRepeatingCharacterinAString obj =
                new FirstNonRepeatingCharacterinAString();
        char c = obj.firstNonRepeatingCharacter(str);
        System.out.println(c);
    }
}

Upvotes: 0

Views: 599

Answers (1)

CodeBlind
CodeBlind

Reputation: 4569

Your question about whether you "can use this code" is a little ambiguous - if you wrote it, I'd think you can use it :)

As for the complexity, it is O(n) where n is the number of characters in the String. To count the number of occurrences, you must iterate over the entire String, plus iterate over them again to find the first one with a count of 1. In the worst case, you have no non-repeating characters, or the only non-repeating character is the last one. In either case, you have to iterate over the whole String once more. So it's O(n+n) = O(n).

EDIT

There is a bug in your code, by the way. Because you are using an insertion-order LinkedHashMap, each call to put(Character,Integer) results in a re-ordering of the underlying list. You should probably use a LinkedHashMap<Character,int[]> instead, and check for the presence of keys before putting. If they exist, then merely increment the value stored in the int[] to avoid re-ording the map by making another put call. Even so, the resulting list will be in reverse order from the way you iterate over it, so the first non-repeating character will be the last one you find when iterating over it whose value is 1. Alternatively, you could just iterate in reverse in your first for loop, then you avoid having to always go through the entire Entry set if the first non-repeating character comes sooner than the final character in the original String.

Upvotes: 2

Related Questions