Sort List of Strings by Characters In Java

Question

I am trying to write a program to order a list of strings by most least frequent characters within the list. For example, if the list was [apple, orange, banana] the letter frequency within the list would be a - 5, n - 3, p - 2, e - 2, l- 1, o - 1, r - 1, g - 1, b - 1. Since orange contains the most least frequent letters, the program would return orange, then apple then banana.

So far I've written the code that orders all the letters in the list by frequency. But I need to apply that to find which string contains the most least frequent letters.

Here is my code:

    Map<Character, Integer> elemCount = new LinkedHashMap<>();
    for (String word : words)
    {
        for (int i = 0; i  < word.length(); i++)
        {
            if (elemCount.containsKey(word.charAt(i)))
            {
                elemCount.put(word.charAt(i), elemCount.get(word.charAt(i)) + 1);
            }
            else
            {
                elemCount.put(word.charAt(i), 1);
            }
        }
    }
    ArrayList<Character> sortedElems = new ArrayList<>();
    elemCount.entrySet().stream().sorted(Collections.reverseOrder
    (Map.Entry.comparingByValue())).forEach(entry -> 
    { 
        for (int i = 1; i <= entry.getValue(); i++)
        {
            sortedElems.add(entry.getKey());
        }
    }
    );
    System.out.println(sortedElems);

Answer 1

public class Main {
    public List<String> sortAccordingly(List<String> unsortedList ) {
        List<String> sorted=new ArrayList<>();

        Map<String,Integer> freq=new TreeMap();
        for(String s:unsortedList) {
            Map<Character, Integer> fq = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                if (fq.containsKey(s.charAt(i)))
                    fq.replace(s.charAt(i), fq.get(s.charAt(i)) + 1);
                else
                    fq.put(s.charAt(i), 1);
            }
            freq.put(s, Collections.max(fq.values()));
        }
        Map<String,Integer> sortedOne=freq.entrySet().stream().sorted(Map.Entry.comparingByValue()).collect(Collectors.toMap(Map.Entry::getKey,Map.Entry::getValue,(e1,e2)->e1,LinkedHashMap::new));
        sortedOne.putAll(freq);
        sorted.addAll(sortedOne.keySet());
        return sorted;

    }


    public static void main(String[] args) {
        List <String> list=new ArrayList<>();
        list.add("apple");
        list.add("orange");
        list.add("banana");
        System.out.println(new Main().sortAccordingly(list));

    }
}

You can use comparator

Comparator<String> valueCompare=new Comparator<String>() {
            @Override
            public int compare(String s, String t1) {
                return freq.get(s).compareTo(freq.get(t1));
            }
        };

instead of

Map<String,Integer> sortedOne=freq.entrySet().stream().sorted(Map.Entry.comparingByValue()).collect(Collectors.toMap(Map.Entry::getKey,Map.Entry::getValue,(e1,e2)->e1,LinkedHashMap::new));

after that function will be

public List<String> sortAccordingly(List<String> unsortedList ) {
        List<String> sorted=new ArrayList<>();

        Map<String,Integer> freq=new TreeMap();
        Comparator<String> valueCompare=new Comparator<String>() {
            @Override
            public int compare(String s, String t1) {
                return freq.get(s).compareTo(freq.get(t1));
            }
        };
        for(String s:unsortedList) {
            Map<Character, Integer> fq = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                if (fq.containsKey(s.charAt(i)))
                    fq.replace(s.charAt(i), fq.get(s.charAt(i)) + 1);
                else
                    fq.put(s.charAt(i), 1);
            }
            freq.put(s, Collections.max(fq.values()));
        }
        Map<String,Integer> sortedOne=new TreeMap<>(valueCompare);
        sortedOne.putAll(freq);
        sorted.addAll(sortedOne.keySet());
        return sorted;

    }

Answer 2

try the below code:

public static void main(String[] args){
        List<String> list = new ArrayList<String>();
        list.add("apple");
        list.add("banana");
        list.add("orange");
        System.out.println(leastFrequentString(list));

    }


    private static Set<String> leastFrequentString(List<String> list){
        Map<String, Integer> mapStringToFrequency = new HashMap<>();
        for(String s:list){
            Map<Character, Integer> mapCharacterToFrequency =  wordFrequency(s);
            int totalScore = 0;
            for(Character c:mapCharacterToFrequency.keySet()){
                if(mapCharacterToFrequency.get(c)>1){
                    totalScore+=1;
                }
            }
            mapStringToFrequency.put(s,totalScore);
        }
        HashMap sortByValue =  sortByValue(mapStringToFrequency);
        return sortByValue.keySet();
    }

    private static Map<Character,Integer> wordFrequency(String s){
        Map<Character, Integer> mapCharacterToFrequency = new HashMap<Character, Integer>();
        for(Character c: s.toCharArray()){
            if(mapCharacterToFrequency.containsKey(c)){
                int frequency = mapCharacterToFrequency.get(c);
                frequency +=1;
                mapCharacterToFrequency.replace(c,frequency);
            }else{
                mapCharacterToFrequency.put(c,1);
            }
        }
        return mapCharacterToFrequency;
    }

    private static LinkedHashMap<String, Integer> sortByValue(Map<String, Integer> hm)
    {
        // Create a list from elements of HashMap
        List<Map.Entry<String, Integer> > list =
                new LinkedList<>(hm.entrySet());

        // Sort the list
        list.sort(Comparator.comparing(Map.Entry::getValue));

        // put data from sorted list to HashMap
        LinkedHashMap<String, Integer> temp = new LinkedHashMap<>();
        for (Map.Entry<String, Integer> aa : list) {
            temp.put(aa.getKey(), aa.getValue());
        }
        return temp;
    }

Answer 3

You can divide the solution to these steps:

• Find the least frequent letters. In your fruit example these letters are l, o, r, g, and b - all have frequency 1.
• Count how many of these letters are contained in each word: apple has 1, orange has 3, banana has 1
• Sort the words according to that count

This is how you can find the least frequent letters. First find the lowest frequency by iterating the elemCount map. Then iterate over the map again to find the letters with the lowest frequency:

        int lowestFrequency = ...result from
        List<Character> leastFrequentLetters = new ArrayList<>();
        for (Map.Entry<Character, Integer> entry : elemCount.entrySet()) {
            if (entry.getValue() == lowestFrequency) {
                leastFrequentLetters.add(entry.getKey());
            }
        }

This is how you can count how many of the letters of a given word are in leastFrequentLetters:

        int count = 0;
        for (char c: word.toCharArray()) {
            if (leastFrequentLetters.contains(c)) {
                count = count + 1;
            }
        }

Once you have a method to retrieve or compute this count for each word, you can sort the words by it. Makes sense?

Answer 4

If you have a list as you suggested: [apple, orange, banana] with letter frequency a - 5, n - 3, p - 2, e - 2, l- 1, o - 1, r - 1, g - 1, b - 1

As I can see you have already written the code to get these frequencies

Next step is to:

iterate over the list elements -> sum frequencies of each letter for apple, orange and banana -> sort! so you can get them in correct order.

Hope this helps.