Java 2 solutions, using map


  • 0
    M

    Time: O(nlgn), Space: O(n)

    public class Solution {
        public String frequencySort(String s) {
            Map<Character, Integer> map = new HashMap<>();
            for(int i=0; i<s.length(); i++){
                char c = s.charAt(i);
                Integer freq = map.getOrDefault(c, 0);
                map.put(c, freq+1);
            }
            Tuple[] tuples = new Tuple[map.size()];
            int i=0;
            for(Map.Entry<Character, Integer> entry : map.entrySet()){
                tuples[i] = new Tuple(entry.getKey(), entry.getValue());
                i++;
            }
            Arrays.sort(tuples);
            StringBuilder sb = new StringBuilder();
            for(Tuple tup : tuples){
                for(int t=0; t<tup.freq; t++){
                    sb.append(tup.c);
                }
            }
            return sb.toString();
        }
        
        class Tuple implements Comparable<Tuple>{
            char c;
            int freq;
            Tuple(char c, int freq){
                this.c = c;
                this.freq = freq;
            }
            @Override
            public int compareTo(Tuple tup){
                return tup.freq-freq;
            }
        }
        
    }
    

    Time: O(n), Space: O(n + maxFreq)

    public class Solution {
        public String frequencySort(String s) {
            if(s==null || s.length()<=1) return s;
            Map<Character, Integer> map = new HashMap<>();
            int maxFreq = 0;
            for(int i=0; i<s.length(); i++){
                char c = s.charAt(i);
                Integer freq = map.getOrDefault(c, 0) + 1;
                map.put(c, freq);
                maxFreq = Math.max(maxFreq, freq);
            }
            StringBuilder[] arr = new StringBuilder[maxFreq+1];
            for(Map.Entry<Character, Integer> entry : map.entrySet()){
                int freq = entry.getValue();
                char c = entry.getKey();
                if(arr[freq] == null)
                    arr[freq] = new StringBuilder();
                for(int i=0; i<freq; i++)
                    arr[freq].append(c);
            }
            StringBuilder sb = new StringBuilder();
            for(int i=maxFreq; i>0; i--){
                if(arr[i] != null)
                    sb.append(arr[i].toString());
            }
            return sb.toString();
        }
    }
    

Log in to reply
 

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