This is the question that I was asked in an interview. Couldn't do it on the spot and I can't seem to work out the printing by arranging in ascending order part.

The question was:

Print the word on following pattern in ascending order of number of occurrence : abbccbddddeeeee

a

cc

bbb

dddd

eeeee

String test = "abbccbdddddddeeeee";
    
    List<Character> orderedList = new ArrayList<Character>();
    List<Integer> orderedNumber = new ArrayList<Integer>();
    
    char[] testing = test.toCharArray();
    
    int value = 1;
    
    Map<Character, Integer> pattern = new HashMap<Character, Integer>();
    
    for(int i = 0; i < testing.length; i  ) {
        value = 1;
        if(!pattern.containsKey(testing[i])) {
        pattern.put(testing[i], value);
        
        for(int j = i   1; j < test.length(); j  ) {
            if(testing[i] == testing[j]) {
                value = pattern.get(testing[i]);
                value  = 1;
                pattern.replace(testing[i], value);
                
            }
        }
        orderedList.add(testing[i]);
        orderedNumber.add(value);
        }
    
    }
    

This is for the printing part but as you can see. I have little success in it.

    System.out.println(orderedList);
    System.out.println(orderedNumber);

    int minNumber = 0;
    int minIndex = 0;
    
    for(int i = 0; i < orderedList.size(); i  ) {
        minNumber = pattern.get(orderedList.get(i));
        int maxNumber = 0;
        for(int j = i  1; j < orderedList.size(); j  ) {
            if(minNumber > pattern.get(orderedList.get(j))) {
                minNumber = pattern.get(orderedList.get(j));
                maxNumber = pattern.get(orderedList.get(i));
            }
                
        }
        System.out.println(minNumber);

            
    }

CodePudding user response：

This is a basic counting sort. You use an array of int to count the occurrence of each character. Then use the array to print them in ascending order. The indices 0-26 map to 'a' to 'z'.

    public static void main(String[] args) {
        String s = "abbccbddddeeeee";
        int[] a = new int[26];
        for(char c: s.toCharArray())
           a[c-'a']  ;
        
        for(int i=0; i<a.length; i  ){
          char c = (char) (i 'a');
          for(int j=0; j<a[i]; j  ){
            System.out.print(c);
          }
          if (a[i]>0) 
             System.out.println();
        }
    }

CodePudding user response：

With your idea of using Map you were on the right track.

Imperative approach

Main steps:

• Generate a map of frequencies for each symbol in the given string.

• Sort the map entries based on values. Obviously, it's not doable withing a map, we need a different collection for that. We can dump map entries into a List and sort it.

• Print the contents of the list.

That's how it can be implemented:

public static void printFrequencyPattern(String str) {

    Map<Character, Integer> frequencies = getFrequencies(str);
    List<Map.Entry<Character, Integer>> sortedEntries = toSortedEntryList(frequencies);
    
    for (Map.Entry<Character, Integer> entry: sortedEntries) {
        System.out.println(entry.getKey().toString().repeat(entry.getValue()));
    }
}

public static Map<Character, Integer> getFrequencies(String str) {
    Map<Character, Integer> frequencies = new HashMap<>();
    for (int i = 0; i < str.length(); i  ) {
        frequencies.merge(str.charAt(i), 1, Integer::sum);
    }
    return frequencies;
}

public static List<Map.Entry<Character, Integer>> toSortedEntryList(Map<Character, Integer> frequencies) {
    
    List<Map.Entry<Character, Integer>> sortedEntries = new ArrayList<>(frequencies.entrySet());
    sortedEntries.sort(Map.Entry.comparingByValue());
    
    return sortedEntries;
}

main()

public static void main(String[] args) {
    String test = "abbccbdddddddeeeee";
    printFrequencyPattern("abbccbdddddddeeeee");
}

Output:

a
cc
bbb
eeeee
ddddddd

Stream-based Solution

In case if you're comfortable with using Stream IPA, here's a one-liner which everything as the code above within a single statement.

The idea behind the code is mostly the same, collector toMap() generates a map of frequencies. Then a stream of its entries gets created and sorted by value of each entry.

str.codePoints()
    .boxed()
    .collect(Collectors.toMap(
        Function.identity(),
        ch -> 1,
        Integer::sum
    ))
    .entrySet().stream()
    .sorted(Map.Entry.comparingByValue())
    .forEachOrdered(entry -> 
        System.out.println(Character.toString(entry.getKey()).repeat(entry.getValue()))
    );

CodePudding user response：

Here is one way.

First, create some random data. I wanted there to be the same number of some elements to allow for sorting in lexical order if the counts were equal.

String s = "abbcccddddeeeeffffffggggggg";
List<String> list =
        new ArrayList<>(Arrays.stream(s.split("")).toList());
Collections.shuffle(list);

Now define a comparator to use in the sort - first on count, then on lexical key. Doing it outside the stream avoids clutter.

 Comparator<Entry<String, Long>> comp = Entry
                    .<String, Long>comparingByValue()
                    .thenComparing(Entry.comparingByKey());

Then stream the list and do a frequency count. The key will be the letter and the count will be its frequency of occurrences. Take the resulting entrySet of the map and sort first based on count, then based on lexical order. Then print using the Entry fields.

list.stream()
        .collect(Collectors.groupingBy(a -> a,
                Collectors.counting()))
        .entrySet().stream().sorted(comp)
        .forEach(e -> System.out.println(
                e.getKey().repeat(e.getValue().intValue())));

prints

a
bb
ccc
dddd
eeee
ffffff
ggggggg