1

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?

fscore
  • 2,567
  • 7
  • 40
  • 74

3 Answers3

2

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}

Tdorno
  • 1,571
  • 4
  • 22
  • 32
  • This is quadratic time.. Isnt it possible in O(n) – fscore May 10 '14 at 02:36
  • @fscore I don't think so, based on the number of comparisons. Do you have to have linear time as well as a Hashmap? – Tdorno May 10 '14 at 02:38
  • get(c)++ gives me a error.. also Why are you using hashmap instead of a hashtable? – fscore May 10 '14 at 02:40
  • @fscore whoops, forgot to add the `map` caller. See edit. I pasted my C approach, sorry. – Tdorno May 10 '14 at 02:44
  • I want to find if a string is unique or not.. this only results in counting unique characters in a string.. – fscore May 10 '14 at 02:48
  • What do you mean by "if a string is unique" you have values stored in you hashmap now (in my example everything is stored under the first key `map.put(c, 1 /*1 is the first key*/)`). Just store other string at different keys and make your comparisons then. – Tdorno May 10 '14 at 02:50
  • @Tdorno It still had a few compilation issues I made an update but I'm not sure how those get approved... – Jeff Ward May 10 '14 at 02:50
  • when I ran your code and print the hashmap, it gives this fpr hello: {e=1, o=1, l=1, h=1} whereas I want, {e=1, o=1, l=2, h=1} – fscore May 10 '14 at 02:52
  • @Tdorno This should be updated `map.put(c, map.get(c++));` it should be `map.put(c, map.get(c) + 1);` the `c++` would not do what you want. – Jeff Ward May 10 '14 at 02:53
  • @fscore That's because the numbers are the key associated with that stored string, not each letter occurrence. – Tdorno May 10 '14 at 02:53
  • @JeffWard Ahh, I didn't catch that. My original implementation works for me in `C`, I kinda ran through it quickly to port it over to `Java` for @fscore. Thanks for the fix. – Tdorno May 10 '14 at 02:56
  • Why are you using hashmap instead of a hashtable? – fscore May 10 '14 at 02:56
  • @fscore Normally more optimal, swapping it to a hashtable will do the same thing. See edit. – Tdorno May 10 '14 at 02:58
  • 1
    @fscore [differences-between-hashmap-and-hashtable](http://stackoverflow.com/questions/40471/differences-between-hashmap-and-hashtable) – Jeff Ward May 10 '14 at 02:58
  • 1
    @fscore Knowledge is power: http://stackoverflow.com/questions/40471/differences-between-hashmap-and-hashtable – Tdorno May 10 '14 at 02:58
  • But how is it more optimal in this particular solution? Can you explain in this example? – fscore May 10 '14 at 02:59
  • 1
    @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). – Jeff Ward May 10 '14 at 03:02
2

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;
}
Hunter McMillen
  • 59,865
  • 24
  • 119
  • 170
  • +1 I have basically same idea but removed since you posted it 1 min before me =) – abc May 10 '14 at 02:45
0

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)", "");
Bohemian
  • 412,405
  • 93
  • 575
  • 722