Finding kth frequency letter in a string of characters

Question

I have a string say "aaabbacccd" here count[a]=4 count[b]=2 count[c]=3 and count[d]=1 . I have to find character with nth largest frequency. In the above string the character with 3rd highest frequency is b (because 1<2<3<4) and count[b]=2

The straight forward solution is storing character Vs frequency in a map and sorting the values using sorting collection by value method like below

public class MapUtil {
public static <K, V extends Comparable<? super V>> Map<K, V> 
    sortByValue(Map<K, V> map) {
    List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>(map.entrySet());
    Collections.sort( list, new Comparator<Map.Entry<K, V>>() {
        public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) {
            return (o1.getValue()).compareTo( o2.getValue() );
        }
    });

    Map<K, V> result = new LinkedHashMap<K, V>();
    for (Map.Entry<K, V> entry : list) {
        result.put(entry.getKey(), entry.getValue());
    }
    return result;
}

}

I tried solving this problem using tree-map to maintain the characters in sorted order based on the count. But all i ended up with was violating the equality and compare to constraint thus my map ending with inconsistent values.

So can't this problem be solved using Tree-map or any other data structure in an optimal way ?

Answer 1

Here is a streaming solution:

import java.util.Collections;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;


public class StackOverflow {

  private static class S46330187 {
    public static void main(String[] args) {
      //prints b
      System.out.println(kthMostFrequentChar("aaabbacccd",3));
      //prints b
      System.out.println(kthMostFrequentChar("aaabbacccbbbd",1));
      //prints e
      System.out.println(kthMostFrequentChar("aaabbbcccdddeee",5));

    }

    private static Character kthMostFrequentChar(final String string, final int kth) {
      Map<Integer, Long> counts = string.chars()
          .boxed()
          .collect(Collectors.groupingBy(
              Function.identity(),
              Collectors.counting()
          ));
      return counts.entrySet()
          .stream()
          .sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
          .map(e->(char)e.getKey().intValue())
          .limit(kth)
          .reduce((l,r)->r)
          .orElseThrow(IllegalArgumentException::new);
    }

  }
}