Descending sort of substrings by occurence - Java

Question

Lest's say I have string:

 String test= "AA BB CC BB BB CC BB";

What I would like to do is create String array like this:

 String[]{"BB", "CC", "AA"}

Since B occurred 4 times C did 2 times and A only 1 time.

What would solution for this problem look like?

Answer 1

String test = "AA BB CC BB BB CC BB";
System.out.println(Arrays.deepToString(sort(test)));

Output: [BB, CC, AA]

Code:

public static String[] sort(String test) {
    String[] strings = test.split(" ");
    HashMap<String,Integer> map = new HashMap<String,Integer>();
    for (String s : strings) {
        Integer i = map.get(s);
        if (i != null) {
            map.put(s, i+1);
        } else {
            map.put(s, 1);
        }
    }

    TreeMap<Integer,String> sort = new TreeMap<Integer,String>(Collections.reverseOrder());
    for (Entry<String,Integer> e : map.entrySet()) {
        sort.put(e.getValue(), e.getKey());
    }

    return sort.values().toArray(new String[0]);
}

Answer 2

What you could do is something like this (rough code):

String[] myOccurences = test.split(" ");

Then:

HashMap<String,Integer> occurencesMap = new HashMap<String,Integer>()

for( String s : myOccurences ){
    if( occurencesMap.get( s ) == null ){
        occurencesMap.put(s, 1);
    } else {
        occurencesMap.put(s, occurencesMap.get(s)++ );
    }
}

Edit: The actual sorting (again rough code and unchecked):

List<String> mapKeys = new ArrayList<String>(occurencesMap.keySet()); // Keys
List<Integer> mapValues = new ArrayList<Integer>(occurencesMap.values()); // Values

TreeSet<Integer> sortedSet = new TreeSet( mapValues ); // Sorted according to natural order                
Integer[] sortedValuesArray = sortedSet.toArray();

HashMap<String,Integer> lhMap = new LinkedHashMap<String,Integer>(); // LinkedHashMaps conserve order

for (int i=0; i<size; i++){
    lhMap.put(mapKeys.get(mapValues.indexOf(sortedArray[i])), sortedValuesArray[i]);
}

mapKeys = new ArrayList<String>(occurencesMap.keySet()); // Keys again, this time sorted
Collections.sort(mapKeys, Collections.reverseOrder()); // Reverse since original ascending

String[] occurencesSortedByDescendingArray = mapKeys.toArray();

Feel free to comment.

Answer 3

If you want to use Guava:

Lists.transform(
  Ordering
    .natural()
    .onResultOf(new Function<Multiset.Entry<String>, Integer>() {
        public Integer apply(Multiset.Entry<String> entry) {
          return entry.getCount();
        }
      })
    .reverse()
    .sortedCopy(
        ImmutableMultiset.copyOf( Splitter.onPattern("\\s+").split(test) ).entrySet()
      ),
  new Function<Multiset.Entry<String>, String>() {
    public String apply(Multiset.Entry<String> entry) {
      return entry.getElement();
    }
  }
);

Answer 4

I am not sure if a method exists for this exact purpose.

However, you could use the String.split() method to split the single string into an array of strings. From there, you could locate unique strings (either by manually checking or adding them all to a set, which would check for duplicates). Track (and increment a counter unique to each unique String) each time you add an element and it is not part of the collection. Then create an array that is sorted based on this count.

A map would be ideal for holding the String/count, as it would maintain the set of unique Strings as keys, and the count for each String as the value.