Problem link ও উৎস
- **Original source:** Classic frequency sort with a heap
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Medium
- **Pattern:** Heap + counting
- **Basic idea inherited from:** `05-hashing` frequency maps — count, তারপর count দিয়ে max-heap
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা string দেওয়া আছে। তোমাকে তার অক্ষরগুলো এমনভাবে সাজিয়ে নতুন string বানাতে হবে যেন **যে অক্ষর বেশিবার এসেছে সে আগে আসে**। একই অক্ষরের সব copy একসাথে থাকবে। সমান frequency-র অক্ষরগুলোর মধ্যে কোন আগে — সেটা নিয়ে problem উদাসীন, যেকোনো বৈধ সাজানোই গ্রহণযোগ্য।
```text
s = "tree" -> "eert" বা "eetr" ('e' দুবার, তাই আগে; 't' আর 'r' একবার করে)
```
### Input ও output {#8-example-input-and-output}
```text
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"
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একজন লাইব্রেরিয়ান একটা তাকে বই সাজাচ্ছেন — যে বই সবচেয়ে বেশি copy আছে সেগুলো সামনে, একসাথে। তিনি আগে গুনে নেন কোন বইয়ের কত copy (frequency map), তারপর বারবার "এখন সবচেয়ে বেশি copy কোনটার?" জিজ্ঞেস করে সেই গাদাটা তাকে রাখেন। সেই "সবচেয়ে বেশি-frequent চট করে দাও" যন্ত্রটাই max-heap।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এ কার্যত নগণ্য।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: frequency map বানিয়ে items-গুলোকে count দিয়ে descending sort করো, তারপর প্রতিটা `char * count` জুড়ে দাও — heap ছাড়াই।
```text
{'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-এ ফিরে আসবে।
### ছবিতে বোঝা {#7-visual-explanation}
`s = "tree"`। আগে count, তারপর max-heap of `(count, char)`:
```text
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" (একটা বৈধ উত্তর)
```
### ছোট input-এ ধাপে ধাপে {#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" (একটা বৈধ সাজানো)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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-এ হারিয়ে যায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#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}
- Top K Frequent Elements —