Find if a string is unique or not

Tag: java , string , hashtable Author: sictoly Date: 2014-04-23

I want to use hashtable to find unique characters as it seems more efficient to me so for example, hello in hashtable would be=> {h:1,e:1,l:2,o:1} & since value is more than 1 then string isnt unique. I know I can do ascii way of counting unique characters but I want to implement the hashtable way.

Please note, I do not want a regex implementation.

static void findHashUnique(String str)
{
    Hashtable<Character, Integer> ht = new Hashtable<Character, Integer>();
    for(int i=0;i<str.length();i++)
    {
        int cnt=1;

        if(!ht.containsKey(str.charAt(i)))
        {
            ht.put(str.charAt(i), cnt);
        }
    }
    System.out.print(ht);
}

I am stuck at the part of how will I first initialize the hashtable & also check if value exists then increment. In case of 'l' it will increment to 2 instead of being 1 since the key is the same. Also Is this solution efficient?

Just use a HashSet (which uses a Hashtable, but so what).
HashSet removes duplicates.. why would I use that?

Best Answer

Here's my approach.

String string = "hello";
Hashtable<Character, Integer> map = new Hashtable<>();
for (int i = 0; i < string.length(); i++) {
   char c = string.charAt(i);
   if (map.containsKey(c)) {
      map.put(c, map.get(c) + 1);
   } else {
      map.put(c, 1);
   }
}
System.out.println(map);

Output: {e=1, o=1, l=2, h=1}

comments:

This is quadratic time.. Isnt it possible in O(n)
@fscore I don't think so, based on the number of comparisons. Do you have to have linear time as well as a Hashmap?
@fscore differences-between-hashmap-and-hashtable
@fscore Knowledge is power:
@fscore did you read the stack overflow link? As it says there you have no synchronization to deal with in this method. So you should use HashMap because it performs better (doesn't have to deal with synchronization issues).

Other Answer1

Well, I don't know exactly what character encodings you will be examining, but if you are constraining yourself to only ASCII characters, you can use a simple array of 128 elements.

public static String uniqueLetters(String s) {
   // storage for ascii characters
   char[] letters = new char[128];

   // mark counts of all letters
   for(int i = 0; i < s.length(); i++) {
      letters[ (int)s.charAt(i) ]++;
   }

   // find unique letters
   String uniques = "";
   for(int i = 0; i < letters.length; i++) {
      if ( letters[i] == 1 ) {
         uniques += Character.toString( (char)letters[i] );
      }
   }

   return uniques;
}

comments:

+1 I have basically same idea but removed since you posted it 1 min before me =)

Other Answer2

To "fix" your code, use a HashSet<Character>, which uses a Hashtable internally, but you don't have to know or worry about that. Just keep adding the chars to the set and you'll be left with a unique set of chars at the end.

To achieve the intention more easily:

String uniqueChars = str.replaceAll("(.)(?=.*\\1)", "");

comments:

Pretty sure he wants a count for each character.
I want to find if a string is unique or not by counting every character
how does this regex work?
@fscore regex matches characters that appear again later in the input, asserted by a look ahead for a back reference to the captured characer