O(n) Easy Java Solution!


  • 0
    S
    1. Keep a count for every character to maintain its frequency.
    2. Keep an array of Set<Character> of size n + 1, where every entry maintains the characters that appear the number of times which equals index in the array.
    e.g sets[5] means all the characters that appeared 5 times.
    3. Finally traverse the array of sets from right to left to build the resulting string.
    
    public class Solution {
        public String frequencySort(String s) {
            if (s == null || s.length() == 0) {
                return "";
            }
            int n = s.length();
            Set<?>[] sets = new Set<?>[n + 1];
            int[] count = new int[256];
            for (char ch : s.toCharArray()) {
                count[ch]++;
                if (count[ch] > 1) {
                    sets[count[ch] - 1].remove(ch);
                }
                if (sets[count[ch]] == null) {
                    sets[count[ch]] = new HashSet<Character>();
                }
                ((Set<Character>)sets[count[ch]]).add(ch);
            }
            StringBuilder sb = new StringBuilder();
            for (int i = n; i > 0; i--) {
                Set<Character> set = (Set<Character>)sets[i];
                if (set != null) {
                    for (char ch : set) {
                        for (int j = 0; j < i; j++) {
                            sb.append(ch);
                        }
                    }
                }
            }
            return sb.toString();
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.