CoderBC CoderBC - 3 months ago 24
Java Question

Find the number of repetitions of a character in a given string and sort them?

Problem statement: Find the repetition of the alphabet characters in a given string (all lower case from a-z only) and sort them from lowest to highest.
If two character have the same number of repetitions, the character with the greater ASCII value is considered to be smaller.

Although the problem is easy, I was trying to use Comparator to sort the final answer instead of using my own sorting. Here is what I did:

private static void importantString(String context) {
HashMap<Character, Integer> importance = new HashMap<Character, Integer>();
String alpha="abcdefghijklmnopqrstuvwxyz";
for(int i=0; i<26; i++){
importance.put(alpha.charAt(i),0);
}
for(int i=0; i<context.length(); i++){
char temp = context.charAt(i);
Integer val = importance.get(temp);
importance.put(temp,++val);
}

//To sort
ArrayList<Map.Entry<Character, Integer>> l = new ArrayList(importance.entrySet());
Collections.sort(l, new Comparator<Map.Entry<Character, Integer>>(){
public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
if (o1.getValue()==o2.getValue()){
if (o1.getKey() > o2.getKey()){
return -1;
}
else{
return 1;
}

}
else {
return o1.getValue().compareTo(o2.getValue());
}
}});
System.out.println(l);
for (Entry<Character, Integer> m: l){
System.out.print(m.getKey()+" ");
}
System.out.println();
}


Now, this definitley works for smaller test cases. For example,

However, I had a very large test case this is what I get (my sorted array is this since the test case string is very large):

[r=38083, p=38223, v=38223, f=38268, e=38269, u=38306, z=38320, k=38341, g=38342, c=38396, o=38418, q=38418, b=38422, n=38467, x=38476, y=38477, l=38525, m=38534, w=38575, d=38580, a=38619, s=38648, t=38653, h=38787, j=38791, i=38839]


Notice, o=38418 and q=38418. In this case 'q' should have a lower precedence than o since it has a higher ASCII value. Yet it does not reflect.

For smaller test cases like oooqqq, I do get the correct results. Any explainations why?

Answer

Your issue is this line:

if (o1.getValue()==o2.getValue()){

You're using reference equality here. Since both sides of == are of type Integers they are tested for reference equality, but only for values -128 <= value <= 127 those Integers are guarantied to be the same objects (see Integer.valueOf which is used for autoboxing here: importance.put(temp,++val);)

You could simply replace this with a comparison of the int values:

if (o1.getValue().intValue()==o2.getValue().intValue()){

Furthermore you could also rewrite the method by using Integer.compareTo and Character.compareTo:

public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
    int res = o1.getValue().compareTo(o2.getValue());
    return res == 0 ? o2.getKey().compareTo(o1.getKey()) : res;
}