O(n) Easy to understand Java Solution


  • 26
    B
    1. Build a map of characters to the number of times it occurs in the string
    2. Create an array where the index of the array represents how many times that character occurred in the String
    3. Iterate from the end of the array to the beginning, and at each index, append each character to the return string that number of times.
    public String frequencySort(String s) {
        if (s == null) {
            return null;
        }
        Map<Character, Integer> map = new HashMap();
        char[] charArray = s.toCharArray();
        int max = 0;
        for (Character c : charArray) {
            if (!map.containsKey(c)) {
                map.put(c, 0);
            }
            map.put(c, map.get(c) + 1);
            max = Math.max(max, map.get(c));
        }
    
        List<Character>[] array = buildArray(map, max);
    
        return buildString(array);
    }
    
    private List<Character>[] buildArray(Map<Character, Integer> map, int maxCount) {
        List<Character>[] array = new List[maxCount + 1];
        for (Character c : map.keySet()) {
            int count = map.get(c);
            if (array[count] == null) {
                array[count] = new ArrayList();
            }
            array[count].add(c);
        }
        return array;
    }
    
    private String buildString(List<Character>[] array) {
        StringBuilder sb = new StringBuilder();
        for (int i = array.length - 1; i > 0; i--) {
            List<Character> list = array[i];
            if (list != null) {
                for (Character c : list) {
                    for (int j = 0; j < i; j++) {
                        sb.append(c);
                    }
                }
            }
        }
        return sb.toString();
    }
    

  • 16
    H

    Nice solution. For character counting we don't need a map, we can just use an array. I did it as follows:

    public class Solution {
        public String frequencySort(String s) {
            int[] freq = new int [256];
            for (char ch: s.toCharArray()) freq[ch]++;
            TreeMap<Integer, List<Character>> tree = new TreeMap<Integer, List<Character>>();
            for (int i=0; i<freq.length; i++) {
                if (freq[i] > 0) {
                    if (!tree.containsKey(freq[i])) {
                        tree.put(freq[i], new LinkedList<Character>());
                    }
                    tree.get(freq[i]).add((char)i);
                }
            }
            StringBuilder sb = new StringBuilder();
            while(tree.size() > 0) {
                Map.Entry<Integer, List<Character>> entry = tree.pollLastEntry();
                for (Character ch: entry.getValue()) {
                    sb.append(new String(new char[entry.getKey()]).replace('\0', ch));
                }
            }
            return sb.toString();
        }
    }
    

  • 0
    B

    @Hx2 Thanks! You are correct if we can assume ascii 256. Good call.


  • 0

    Nice O(N) time solution (and also O(N) space). Another trade-off I can think about is to go another O(N) pass in frequency map to also get min frequency instead of max frequency so that the array length to build could be much shorten if the character frequencies are very close to each other. This will also save time when building string in the expense of an additional pass in frequency to get min frequency.


  • 19
    P

    My code runs in 11ms and i think its faster than yours . I see people are using HashMap/TreeMap which are not at all required. If you know bucket sort then following solution will be easy to understand!

    public String frequencySort(String s) {
            if(s.length() < 3)
                return s;
            int max = 0;
            int[] map = new int[256];
            for(char ch : s.toCharArray()) {
                map[ch]++;
                max = Math.max(max,map[ch]);
            }
            String[] buckets = new String[max + 1]; // create max buckets
            for(int i = 0 ; i < 256; i++) { // join chars in the same bucket
                String str = buckets[map[i]];
                if(map[i] > 0)
                    buckets[map[i]] = (str == null) ? "" + (char)i : (str + (char) i);
            }
            StringBuilder strb = new StringBuilder();
            for(int i = max; i >= 0; i--) { // create string for each bucket.
                if(buckets[i] != null)
                    for(char ch : buckets[i].toCharArray())
                        for(int j = 0; j < i; j++)
                            strb.append(ch);
            }
            return strb.toString();
        }
    

    Check more details here : https://discuss.leetcode.com/topic/66333/super-simple-o-n-bucket-sort-based-java-solution-11-ms-no-fancy-data-structure-needed-inline-comments


  • 0
    D

    @piyush121 Please include the time taken. Nice approach, expanded my toolbox(bucket sort) because of you!


  • 0
    P

    @dev.abkulkar Done! Thanks for the vote !


  • 0
    P

    @Hx2 If you treemap every operation is not o(1), it is log(n).
    So time complexity increases.


  • 1

    Nice Solution! Thanks for sharing. I think some part can be simplified. Here is my Java solution:

    public String frequencySort(String s) {
        int[] count = new int[256];
        StringBuilder sb = new StringBuilder();
        List<List<Integer>> list = new ArrayList<>();
        
        for (int i = 0; i < s.length(); i++) count[s.charAt(i)]++;
        for (int i = 0; i < s.length()+1; i++) list.add(new ArrayList<Integer>());
        for (int i = 0; i < count.length; i++) if (count[i] != 0) list.get(count[i]).add(i);
                
        for (int i = list.size()-1; i >= 0; i--){
            if (list.get(i) != null){
                List<Integer> temp = list.get(i);
                for(int k = 0; k < temp.size(); k++){
                    for (int m = 0; m < i; m++){
                        sb.append(Character.toChars(temp.get(k)));
                    }
                }
            }
        }
        return sb.toString();
    }

  • 0
    F

    Could anyone told me why the time complexity is O(n) in this solution?
    The buildString function doesn't seems like a O(n) method.


  • 1

    @FreeLance said in O(n) Easy to understand Java Solution:

    Could anyone told me why the time complexity is O(n) in this solution?
    The buildString function doesn't seems like a O(n) method.

    The buildString function is still O(N) time complexity even though it has 3 nested loops. At the end of the day, the time complexity in function buildString depends on how many time sb.append(c) is executed. The final result string sb.toString() is simply a reordered string of the given string, so of course, sb.append(c) is executed exactly N times.


  • 0
    A

    @Hx2 Why is array preferable over map? Aren't they using the same amount of space?


  • 1

    @austurela said in O(n) Easy to understand Java Solution:

    @Hx2 Why is array preferable over map? Aren't they using the same amount of space?

    If both arrays and maps can achieve the same purpose, indeed arrays should be always preferable over maps. Even though the space usage are both O(N) in terms of asymptotic sense, arrays are simpler data structure with less space and contiguous memory allocation, which has better performance than maps. While maps/sets are node based containers which suffer memory locality. I am speaking for C++ and Java might differ at some level. Hopefully, it could help.


  • 0
    A

    In this instance, each pollToLastEntry is log(n), making your solution nlogn overall. You could walk through it backwards in O(n) via Collections.reverseOrder.


  • 0
    B

    @Hx2 Why not just use PriorityQueue instead of TreeSet?


  • 0
    V

    For the mapping part can be simplified

    for (char c: s.toCharArray()) {
      map.put(c, map.getOrDefault(c, 0) + 1);
    }
    

  • 0
    Z

    @Hx2 Nice solution. If we can assume ascii 256, using a 2D array could be more simple. It also works with O(n) time and O(1) space.

        public String frequencySort(String s) {
            StringBuffer sb = new StringBuffer();
            int[][] a = new int[256][2];//a[][0] is the character. a[][1] is the frequency
            for(int i=0;i<256;++i)
                a[i][0]=i;
            char temp;
            for(int i=0;i<s.length();++i){
                temp = s.charAt(i);
                    a[temp][1]++;
            }
            Arrays.sort(a,new Comparator<int[]>(){
                public int compare(int[] a,int[] b){
                    return b[1]-a[1];
                }
            });
            for(int i=0;i<256;++i){
                temp = (char)a[i][0];
                for(int j=0;j<a[i][1];++j)
                    sb.append(temp);
            }
            return sb.toString();
        }

  • 0
    R
    This post is deleted!

  • 0

    Java solution use hashmap and heap.

    public String frequencySort(String s) {
      char[] sc = s.toCharArray();
      Map<Character, Integer> map = new HashMap();
      for(char c: sc){
        int val = map.getOrDefault(c, 0) + 1;
        map.put(c, val);
      }    
    
     Comparator<Map.Entry<Character, Integer>> com = Map.Entry.comparingByValue(Comparator.reverseOrder());
      PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue(com);
    
      for(Map.Entry<Character, Integer> entry: map.entrySet()){
        pq.offer(entry);
      }
    
      StringBuilder sb = new StringBuilder();
      while(!pq.isEmpty()){
        Map.Entry<Character, Integer> entry = pq.poll();
        char k = entry.getKey();
        int v = entry.getValue();
        char[] rep = new char[v];
        Arrays.fill(rep, k);
        sb.append(rep);
      }
      return sb.toString();
    }

  • 0
    M
    This post is deleted!

Log in to reply
 

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