Skip to content

008 — Sort Characters By Frequency

Source

  • Original source: Classic frequency sort with a heap
  • Platform: LeetCode — https://leetcode.com/problems/sort-characters-by-frequency/
  • Topic: heap / priority queue
  • Difficulty: Medium
  • Pattern: Heap + counting
  • Basic idea inherited from: 05-hashing frequency maps — count, তারপর count দিয়ে max-heap

1. Problem in simple words

একটা string দেওয়া আছে। তোমাকে তার অক্ষরগুলো এমনভাবে সাজিয়ে নতুন string বানাতে হবে যেন যে অক্ষর বেশিবার এসেছে সে আগে আসে। একই অক্ষরের সব copy একসাথে থাকবে। সমান frequency-র অক্ষরগুলোর মধ্যে কোন আগে — সেটা নিয়ে problem উদাসীন, যেকোনো বৈধ সাজানোই গ্রহণযোগ্য।

s = "tree"  ->  "eert" বা "eetr"   ('e' দুবার, তাই আগে; 't' আর 'r' একবার করে)

2. Which basic idea does this inherit from?

ভিত হলো 05-hashing-এর frequency map — কে কতবার এসেছে গোনা। তারপর 08-এর heap: সেই count-গুলোকে max-heap-এ রেখে বেশি-frequent অক্ষর আগে টেনে বের করা। অর্থাৎ আবার "count, then heap" — তবে এবার top-K না, পুরো order চাই (frequency-descending)।

3. What is the hidden math or logic?

লুকানো logic সরল: output-এ অক্ষরের order = frequency-descending order, আর প্রতিটা অক্ষর তার frequency-সংখ্যকবার repeat হয়। তাই কাজটা = প্রতিটা distinct অক্ষরের count বের করা, count দিয়ে বড় থেকে ছোট সাজানো, তারপর char * count জুড়ে দেওয়া।

4. Which data structure is needed?

দুটো: একটা hash map (অক্ষর → count) আর একটা max-heap of (count, char)। heapq min-heap, তাই max-heap বানাতে count negate করি — top-এ থাকে সবচেয়ে বেশি-frequent অক্ষর।

5. Why this data structure fits

hash map O(n)-এ frequency দেয়। max-heap-এর top সবসময় বর্তমান সবচেয়ে বেশি-frequent অক্ষর — বারবার pop করলে ঠিক যে order-এ output বানাতে হবে সেই order-এই অক্ষর বেরিয়ে আসে। distinct অক্ষর সংখ্যা m (ছোট, যেমন ≤ 62 বা 128); heap ops O(m log m), যা ছোট alphabet-এ কার্যত নগণ্য।

6. Real-life analogy

ভাবো একজন লাইব্রেরিয়ান একটা তাকে বই সাজাচ্ছেন — যে বই সবচেয়ে বেশি copy আছে সেগুলো সামনে, একসাথে। তিনি আগে গুনে নেন কোন বইয়ের কত copy (frequency map), তারপর বারবার "এখন সবচেয়ে বেশি copy কোনটার?" জিজ্ঞেস করে সেই গাদাটা তাকে রাখেন। সেই "সবচেয়ে বেশি-frequent চট করে দাও" যন্ত্রটাই max-heap।

7. Visual explanation

s = "tree"। আগে count, তারপর max-heap of (count, char):

count map:  {'t': 1, 'r': 1, 'e': 2}

max-heap pop order (count, char):
  (2, 'e')  ->  "ee"      (সবচেয়ে বেশি-frequent)
  (1, 't')  ->  "t"
  (1, 'r')  ->  "r"

জোড়া দাও:  "ee" + "t" + "r"  ->  "eetr"   (একটা বৈধ উত্তর)

8. Example input and output

Input : s = "tree"      -> Output: "eert" / "eetr"   (যেকোনো বৈধ)
Input : s = "cccaaa"    -> Output: "cccaaa" / "aaaccc"
Input : s = "Aabb"      -> Output: "bbAa" / "bbaA"   ('A' ≠ 'a')
Input : s = "a"         -> Output: "a"

9. Brute force thinking

প্রথম সরল চিন্তা: frequency map বানিয়ে items-গুলোকে count দিয়ে descending sort করো, তারপর প্রতিটা char * count জুড়ে দাও — heap ছাড়াই।

{'t':1,'r':1,'e':2} -> sort by count desc -> [('e',2),('t',1),('r',1)] -> "ee"+"t"+"r"

10. Why brute force is slow

আসলে এই brute force ধীর নয় — m distinct অক্ষর sort করা O(m log m), heap-ও তাই। পার্থক্য মূলত চিন্তার: heap দেখায় "বারবার সবচেয়ে frequent টেনে বের করা" pattern-টা, যা #6/#10-এর মতো harder problem-এ কাজে লাগে। ছোট alphabet-এ counting sort (bucket by frequency) তো O(n)-এও করা যায় — কিন্তু heap version মনে রাখা সহজ আর general।

11. Key observation

মূল observation: output পুরোপুরি নির্ধারিত হয় frequency দিয়ে — বেশি-frequent অক্ষর আগে, প্রত্যেকে নিজের count-সংখ্যকবার। তাই একবার count পেলে কাজটা নিছক "frequency-descending order-এ অক্ষর বের করা", যা max-heap সরাসরি দেয়।

12. Optimized intuition

dict-এ frequency গোনো। (count, char)-গুলো max-heap-এ ঢালো (count negate)। বারবার pop করো; প্রতিটা pop-এ char * count output-এ জোড়ো। heap খালি হলে থামো। count O(n), heap ops O(m log m), মোট O(n + m log m); ছোট alphabet-এ কার্যত O(n)।

13. Thinking tweak

মোচড়: "string sort করছি" না ভেবে ভাবো "একটা frequency multiset থেকে বারবার সবচেয়ে frequent group টেনে বের করছি।" যেকোনো "arrange by frequency / most frequent first" problem এই count-then-max-heap ছাঁচে পড়ে — আর সেই ছাঁচটাই Task Scheduler, Reorganize String-এ ফিরে আসবে।

14. Step-by-step dry run

Input s = "tree":

  1. count map: {'t': 1, 'r': 1, 'e': 2}
  2. max-heap (negate count): entries (−2,'e'), (−1,'t'), (−1,'r'); top = (−2,'e')
  3. pop (−2,'e') → count 2 → output += "ee"
  4. pop (−1,'t') → count 1 → output += "t" (বা 'r' আগে আসতে পারে — tie)
  5. pop (−1,'r') → count 1 → output += "r"
  6. heap খালি → output = "eetr" (একটা বৈধ সাজানো)

15. Python solution

import heapq
from collections import Counter

def frequency_sort(s):
    freq = Counter(s)                      # O(n): প্রতিটা অক্ষরের count
    # max-heap: count negate করো, সাথে char
    h = [(-count, ch) for ch, count in freq.items()]
    heapq.heapify(h)                       # top = সবচেয়ে বেশি-frequent
    out = []
    while h:
        neg_count, ch = heapq.heappop(h)
        out.append(ch * (-neg_count))      # অক্ষরটা count-বার repeat
    return "".join(out)

# ---- tests (order tie বলে frequency-signature মিলিয়ে check করি) ----
def freq_sig(s):
    # একই multiset + non-increasing run-lengths হলে বৈধ
    from itertools import groupby
    runs = [(ch, len(list(g))) for ch, g in groupby(s)]
    counts = [c for _, c in runs]
    return sorted(s), counts == sorted(counts, reverse=True), \
        sorted(Counter(s).values(), reverse=True)

def is_valid_freq_sort(original, result):
    same_multiset = sorted(original) == sorted(result)
    # প্রতিটা অক্ষর একটানা থাকতে হবে আর run-length non-increasing
    from itertools import groupby
    runs = [(ch, len(list(g))) for ch, g in groupby(result)]
    chars = [ch for ch, _ in runs]
    no_split = len(chars) == len(set(chars))            # কোনো অক্ষর ভাঙেনি
    lengths = [c for _, c in runs]
    non_increasing = lengths == sorted(lengths, reverse=True)
    return same_multiset and no_split and non_increasing

assert is_valid_freq_sort("tree", frequency_sort("tree"))
assert is_valid_freq_sort("cccaaa", frequency_sort("cccaaa"))
assert is_valid_freq_sort("Aabb", frequency_sort("Aabb"))
assert is_valid_freq_sort("a", frequency_sort("a"))
assert frequency_sort("") == ""
print("সব test pass!")

16. Line-by-line code explanation

  • freq = Counter(s) — 05-hashing-এর frequency map; O(n)-এ প্রতিটা অক্ষরের count।
  • h = [(-count, ch) for ...] — count negate করে max-heap entry; top-এ সবচেয়ে বেশি-frequent।
  • heapq.heapify(h) — O(m)-এ heap, m = distinct অক্ষর সংখ্যা।
  • neg_count, ch = heapq.heappop(h) — বর্তমান সবচেয়ে frequent অক্ষর আর তার (negated) count।
  • out.append(ch * (-neg_count)) — অক্ষরটা তার count-সংখ্যকবার repeat করে জোড়ো।
  • return "".join(out) — সব group একসাথে জুড়ে final string।
  • test-এর is_valid_freq_sort — tie বলে নির্দিষ্ট string না মিলিয়ে যাচাই করি: একই অক্ষর-multiset, কোনো অক্ষর ভাঙেনি, আর run-length গুলো non-increasing।

17. Output walkthrough

frequency_sort("tree") section 14 মেনে "eetr" (বা "eert") দেয় — is_valid_freq_sort true (multiset এক, 'e' একসাথে, run-lengths [2,1,1] non-increasing)। "cccaaa" → counts 3,3 → "cccaaa"/"aaaccc", দুটোই বৈধ। "Aabb" → 'A','a' আলাদা, 'b' frequency 2 আগে। "a" ও "" সরাসরি। পাঁচটা assert pass করার পরে print হয়: সব test pass!।

18. Time complexity

O(n + m log m) — count O(n); m = distinct অক্ষর সংখ্যা, heap build + pop O(m log m); output জোড়া O(n)। ছোট fixed alphabet-এ m constant, তাই কার্যত O(n)।

19. Space complexity

O(n) — frequency map + output string, দুটোই সবচেয়ে খারাপ ক্ষেত্রে O(n)। heap শুধু O(m)।

20. Common mistakes

  • max-heap না বানিয়ে min-heap ব্যবহার — তখন কম-frequent অক্ষর আগে আসে, frequency-ascending হয়ে যায়।
  • pop-এর পরে count negate ফেরাতে ভুলে যাওয়া — ch * neg_count দিলে negative repeat, খালি string।
  • অক্ষরকে count-বার repeat না করে একবার করে যোগ করা — frequency তথ্য output-এ হারিয়ে যায়।

21. Which basic problem this inherits from

ভিত্তি 05-hashing-এর frequency map (Counter), আর 08-এর heap (patterns.md Pattern 6-এর "most frequent next" ভাবনা)। এটা #6 (Top K Frequent)-এর আত্মীয় — সেখানে শুধু top-k লাগত, এখানে পুরো frequency-descending order লাগে।

22. Similar harder problems

23. Pattern learned

Count-then-max-heap (full frequency order): "arrange by frequency / most frequent first" দেখলে — Counter দিয়ে count, তারপর (count, char)-এর max-heap থেকে বারবার pop। top-K-র তুলনায় এখানে সবাইকে বের করা হয়, k জনকে না। এই "most frequent first" ছাঁচ scheduling problem-এর হৃদয়।

24. Final summary

ভবিষ্যতের আমাকে: "characters sort by frequency" = Counter + max-heap of (count, char), pop করে char * count জোড়ো। মনে রেখো — frequency-descending মানেই max-heap, আর tie-তে যেকোনো order বৈধ। এই "most frequent টেনে বের করা" reflex-টাই পরে Task Scheduler-এ কাজে দেবে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।