O(N) solution with Bucket Sort


  • 0
    I
    1. Get an alphabetic hash mapping char to frequency (how many times it presents in the string).
    2. Get a frequency hash mapping frequency to an expanded substring.
    3. Bucket Sort on frequency hash
      # O(N) Double bucket sort
      def frequency_sort(s)
        alpha = s.chars.reduce( Hash.new(0) ) do |ha, ch|
          ha[ch] += 1
          ha
        end
    
        frequency = {}
        max_f = 0
        alpha.each do |k, v|
          frequency[v] ||= ""
          frequency[v] << k*v
          max_f = v if max_f < v
        end
    
        max_f.downto(1).reduce("") do |str, f|
          frequency.has_key?(f) ? (str << frequency[f]) : str
        end
      end
    
    

Log in to reply
 

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