Problem link ও উৎস
- **Original source:** LeetCode — Reorganize String
- **Platform:** LeetCode —
- **Topic:** Greedy math tricks → most frequent first, feasibility bound
- **Difficulty:** Medium
- **Pattern:** most frequent first (সবচেয়ে frequent character আগে ছড়াও)
- **Basic idea inherited from:** — (frequency-greedy-র প্রথম উদাহরণ)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা string `s` দেওয়া আছে (যেমন `"aab"`)। তুমি এর অক্ষরগুলো **এমনভাবে সাজাও যাতে কোনো দুটো একই অক্ষর পাশাপাশি না থাকে**।
যদি এমন সাজানো সম্ভব হয়, একটা valid সাজানো রূপ ফেরত দাও; সম্ভব না হলে খালি string `""` ফেরত দাও।
উদাহরণ: `"aab"` → `"aba"` (সম্ভব); `"aaab"` → `""` (অসম্ভব, তিনটা `a`-কে আলাদা করার মতো যথেষ্ট ফাঁক নেই)।
### Input ও output {#6-example-input-and-output}
```text
s -> output (একটা সম্ভাব্য valid রূপ; "" = অসম্ভব)
-----------------------------------------------------------------
"aab" -> "aba"
"aaab" -> "" (a = 3 > (4+1)//2 = 2)
"a" -> "a"
"aabb" -> "abab" (বা "baba")
"vvvlo" -> "vlvov" (v = 3, n = 5, (5+1)//2 = 3 — ঠিক সীমায়, সম্ভব)
```
খেয়াল করো `"vvvlo"`-তে `v` ঠিক `(n+1)//2 = 3` — সীমার গায়ে, তাই **সম্ভব** (বেশি হলে অসম্ভব হতো)। output-এর একাধিক সঠিক রূপ থাকতে পারে; আমরা যেকোনো একটা valid রূপ গ্রহণ করি।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি একটা লম্বা টেবিলে অতিথিদের বসাচ্ছ, আর নিয়ম — **একই পরিবারের দুজন পাশাপাশি বসবে না** (যাতে তারা শুধু নিজেদের মধ্যে গল্প না করে)।
সবচেয়ে বড় পরিবারটাই সবচেয়ে বড় সমস্যা — তাদের যদি শেষে বসাও, ফাঁক পাবে না, দুজন পাশাপাশি পড়ে যাবে। তাই **বড় পরিবারটাকে আগে, এক চেয়ার পর পর ছড়িয়ে বসাও** (চেয়ার 0, 2, 4...)। তারপর বাকি ছোট পরিবারদের মাঝের ফাঁকা চেয়ারে। আর যদি একটা পরিবারই অর্ধেকের বেশি লোক হয়, তাহলে যত চালাকিই করো, দুজন পাশাপাশি পড়বেই — তখন সাজানো অসম্ভব।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা frequency-greedy-র প্রথম উদাহরণ, তাই আগের কোনো greedy-র উপর সরাসরি দাঁড়ায় না (`inherited from: —`)।
তবে এর হাতিয়ার চেনা: **frequency count** (`Counter` — কোন অক্ষর কতবার, place-value/counting-এর সেই পুরোনো অভ্যাস) আর একটা **feasibility check** (গণিতের সীমা দিয়ে আগেই "সম্ভব কি না" বলা)। নতুনত্ব হলো greedy idea-টা: "সবচেয়ে frequent আগে"। আর এখানেই heap-এর teaser — dynamic ভাবে "এখন সবচেয়ে frequent কে?" জানতে চাইলে max-heap লাগে (পুরো গল্প `../../08-heap-priority-queue/`-তে)।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
দুটো জিনিস।
- **Feasibility bound:** কোনো অক্ষরের count যদি `(n + 1) // 2`-এর বেশি হয় (n = মোট দৈর্ঘ্য), তাহলে সাজানো **অসম্ভব** — ওই অক্ষরকে আলাদা রাখার মতো যথেষ্ট ফাঁক নেই। (যেমন `"aaab"`-এ `a` আছে 3টা, কিন্তু `(4+1)//2 = 2` — তাই অসম্ভব।)
- **Greedy placement:** সবচেয়ে বেশি frequency-র অক্ষরটাই সবচেয়ে বড় হুমকি; তাকে আগে আগে বসাও — প্রথমে সব even index (0, 2, 4, ...), তারপর odd index (1, 3, 5, ...)। এতে একই অক্ষর কখনো পাশাপাশি পড়ে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরাসরি, কিন্তু ধীর চিন্তা — **সব permutation চেষ্টা করো**, প্রতিটার মধ্যে দেখো কোনো দুটো পাশাপাশি অক্ষর সমান কিনা; প্রথম যেটা valid সেটাই ফেরত দাও:
```python
from itertools import permutations
def reorganize_brute(s):
for perm in permutations(s):
ok = all(perm[i] != perm[i + 1] for i in range(len(perm) - 1))
if ok:
return "".join(perm)
return ""
```
সব সাজানো দেখে বলে এটা সবসময় সঠিক — feasibility-ও সঠিক ধরে (কোনো valid না থাকলে `""`)। ধীর, কিন্তু আমাদের যাচাইয়ের মাপকাঠি।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
n অক্ষরের permutation আছে **n!** — তাই এই brute factorial-ভাবে বিস্ফোরিত হয়। n = 10 হলেই প্রায় 36 লক্ষ permutation, n = 13-এ কোটি ছাড়িয়ে যায় — সম্পূর্ণ অসম্ভব।
```text
সব permutation = n! → factorial বিস্ফোরণ
brute force : O(n! · n) (ভয়ানক ধীর)
greedy : O(n log k) (count + frequency-order placement; k = আলাদা অক্ষর)
```
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল observation: **সবচেয়ে frequent অক্ষর আগে ছড়িয়ে দিলে আর কখনো পাশাপাশি পড়ার ভয় থাকে না।** আগে feasibility check, তারপর even→odd index-এ বসানো:
```python
from collections import Counter
def reorganize(s):
n = len(s)
cnt = Counter(s)
max_freq = max(cnt.values())
if max_freq > (n + 1) // 2:
return "" # অসম্ভব
res = [None] * n
i = 0
for ch, f in cnt.most_common(): # frequency descending
for _ in range(f):
res[i] = ch
i += 2
if i >= n:
i = 1 # even ঘর শেষ → odd ঘরে যাও
return "".join(res)
```
**Greedy choice:** frequency-র অবরোহী ক্রমে অক্ষর নাও; প্রতিটা অক্ষরকে পরবর্তী ফাঁকা index-এ বসাও (আগে সব even, তারপর সব odd)।
**কেন কাজ করে (এক লাইন):** even index গুলো (0, 2, 4...) পরস্পর থেকে অন্তত 2 দূরে, তাই সবচেয়ে frequent অক্ষর — যার count `(n+1)//2`-এর বেশি নয় — পুরোটা শুধু even index-এই এঁটে যায়, ফলে তার দুটো কপি কখনো পাশাপাশি পড়ে না; আর পরের অক্ষরগুলোও একই ক্রমে ফাঁকা ঘরে বসায় কোনো সংঘর্ষ হয় না।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
এক লাইনের "আহা!":
> "সবচেয়ে বেশিবার থাকা অক্ষরটাই একমাত্র আসল হুমকি — তাকে আগে এক ঘর পর পর (even index) ছড়িয়ে দাও, বাকিরা ফাঁকে আপনাআপনি বসে যাবে।"
আর feasibility-র tweak: চেষ্টা করার আগেই `(n+1)//2` দিয়ে "অসম্ভব" ধরে ফেলা — অযথা সাজানোর চেষ্টা বাঁচে। এই দুই মিলেই factorial brute-কে প্রায় linear-এ নামায়।
### ছবিতে বোঝা {#5-visual-explanation}
`s = "aaabbc"` (n = 6, a:3, b:2, c:1) — most frequent আগে, even index-এ:
```text
index : 0 1 2 3 4 5
ফাঁকা : _ _ _ _ _ _
a (3টা) → even index 0,2,4 : a _ a _ a _
b (2টা) → পরের ফাঁকা index 1,3: a b a b a _
c (1টা) → পরের ফাঁকা index 5 : a b a b a c
ফল: "ababac" → কোনো দুটো একই অক্ষর পাশাপাশি নেই ✓
```
feasibility bound-এর ছবি — কেন `(n+1)//2`:
```text
n = 4 → সর্বোচ্চ আলাদা রাখা যায়: _ X _ X বা X _ X _
মানে একটা অক্ষর সর্বোচ্চ 2 বার = (4+1)//2
"aaab": a = 3 > 2 → 3টা a-কে আলাদা রাখার ফাঁক নেই → অসম্ভব
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`s = "aaabbc"` (n = 6) ধীরে চালাই। `Counter`: a:3, b:2, c:1। `(6+1)//2 = 3`; max_freq = 3 ≤ 3, তাই সম্ভব।
`res = [_, _, _, _, _, _]`, শুরুতে `i = 0`।
| অক্ষর (frequency ক্রমে) | বসানো index | i-এর পরিবর্তন | res |
| --- | --- | --- | --- |
| a (1/3) | 0 | i = 2 | a _ _ _ _ _ |
| a (2/3) | 2 | i = 4 | a _ a _ _ _ |
| a (3/3) | 4 | i = 6 ≥ 6 → i = 1 | a _ a _ a _ |
| b (1/2) | 1 | i = 3 | a b a _ a _ |
| b (2/2) | 3 | i = 5 | a b a b a _ |
| c (1/1) | 5 | i = 7 (শেষ) | a b a b a c |
ফল: `"ababac"` — কোনো দুটো একই অক্ষর পাশাপাশি নেই। লক্ষ করো `a` (সবচেয়ে frequent) পুরোটা even index-এ বসেছে, তাই নিরাপদ।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
from collections import Counter
def reorganize(s):
"""most frequent first — valid rearrangement বা "" (অসম্ভব হলে)।"""
n = len(s)
cnt = Counter(s)
max_freq = max(cnt.values()) if cnt else 0
if max_freq > (n + 1) // 2:
return "" # অসম্ভব
res = [None] * n
i = 0
for ch, f in cnt.most_common(): # frequency descending
for _ in range(f):
res[i] = ch
i += 2
if i >= n:
i = 1 # even ঘর শেষ → odd ঘরে যাও
return "".join(res)
def is_valid(arrangement, original):
"""arrangement কি original-এর permutation আর পাশাপাশি কোনো অক্ষর সমান নয়?"""
if Counter(arrangement) != Counter(original):
return False
return all(arrangement[i] != arrangement[i + 1] for i in range(len(arrangement) - 1))
def feasible_brute(s):
"""কোনো valid rearrangement আছে কিনা — সব permutation দেখে (নির্ভুল, ধীর)।"""
from itertools import permutations
for perm in permutations(s):
if all(perm[i] != perm[i + 1] for i in range(len(perm) - 1)):
return True
return False
# --- ছোট test (সব pass করা উচিত) ---
# সরাসরি feasibility
assert reorganize("aaab") == "" # অসম্ভব
assert reorganize("a") == "a"
# যেখানে সম্ভব, output valid permutation আর কোনো adjacent সমান নয়
for s in ["aab", "aabb", "vvvlo", "aaabbc", "aabbcc"]:
out = reorganize(s)
assert out != "", f"{s} সম্ভব হওয়া উচিত"
assert is_valid(out, s), f"{s} → {out} invalid!"
# greedy-র feasibility আর brute-এর feasibility ছোট সব string-এ একমত
import itertools
for n in range(1, 7):
for combo in itertools.combinations_with_replacement("abc", n):
s = "".join(combo)
greedy_ok = (reorganize(s) != "")
assert greedy_ok == feasible_brute(s), f"{s}: greedy {greedy_ok} vs brute"
if greedy_ok:
assert is_valid(reorganize(s), s)
print(reorganize("aab")) # aba (বা অন্য valid)
print(reorganize("aaab")) # "" (অসম্ভব)
print(reorganize("aabb")) # abab (বা অন্য valid)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
cnt = Counter(s)
max_freq = max(cnt.values()) if cnt else 0
if max_freq > (n + 1) // 2:
return ""
```
প্রতিটা অক্ষরের গণনা বের করি; সবচেয়ে বেশি গণনা যদি `(n+1)//2` ছাড়ায়, সাজানোই অসম্ভব — সঙ্গে সঙ্গে `""`।
```text
res = [None] * n
i = 0
for ch, f in cnt.most_common():
```
ফলাফলের জন্য n ঘরের একটা তালিকা; `most_common()` অক্ষরগুলো frequency-র অবরোহী ক্রমে দেয় — সবচেয়ে বড় হুমকি আগে।
```text
res[i] = ch
i += 2
if i >= n:
i = 1
```
অক্ষরটা বর্তমান index-এ বসাই, তারপর 2 ঘর লাফাই (even চেইন)। even ঘর শেষ হলে (`i >= n`) odd চেইনে (index 1) যাই। এই "2 করে লাফ" নিশ্চিত করে একই অক্ষর কখনো পাশাপাশি পড়ে না।
বাকি `is_valid`, `feasible_brute` যাচাইয়ের যন্ত্র — output সত্যিই permutation কিনা ও adjacent কোনো সমান নেই কিনা দেখে, আর সব ছোট string-এ greedy-র feasibility brute-এর সাথে মেলায়।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে (একটা সম্ভাব্য রূপ — placement নিয়ম fixed বলে এই বাস্তবায়নে নির্দিষ্ট):
```text
aba
<- এই লাইন আসলে খালি string (অসম্ভব)
abab
সব test pass!
```
প্রথম line `"aab"` → `"aba"`; দ্বিতীয় `print` খালি string ছাপে (`"aaab"` অসম্ভব, তাই ফাঁকা লাইন); তৃতীয় `"aabb"` → `"abab"`। তার আগে সব `assert` (feasibility + validity + ছোট সব string-এ brute মিলিয়ে) চুপচাপ pass করেছে, তাই শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n log k)** (বা O(n)) — count করা O(n); `most_common()` k টা আলাদা অক্ষর sort করে (O(k log k)); placement O(n)। k সাধারণত ছোট (যেমন 26) বলে কার্যত linear। brute force-এর O(n!) থেকে অকল্পনীয় উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(n)** — ফলাফলের `res` তালিকা আর `Counter` (O(k)) লাগে। output নিজেই n দৈর্ঘ্যের, তাই O(n) অনিবার্য।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **Feasibility check না করা** — সবচেয়ে frequent অক্ষরের count `(n+1)//2`-এর বেশি হলে অসম্ভব; আগে এটা না দেখলে ভুল (পাশাপাশি সমান) output আসবে।
- **`(n+1)//2`-এর বদলে `n//2` ব্যবহার** — বিজোড় n-এ সীমা `(n+1)//2`; `n//2` লিখলে কিছু সম্ভব case-কে ভুলভাবে অসম্ভব বলবে।
- **Even index ভরার আগে odd-এ চলে যাওয়া** — সব even (0,2,4...) আগে, তারপর odd (1,3...); ক্রম উল্টে গেলে একই অক্ষর পাশাপাশি পড়তে পারে।
- **শুধু একটা valid উত্তর হয় ধরে নেওয়া** — একাধিক valid রূপ থাকতে পারে; কোনো সঠিক রূপই গ্রহণযোগ্য (তাই যাচাইয়ে exact string না মিলিয়ে validity দেখা ভালো)।
- **খালি বা single-char string না সামলানো** — `""` বা `"a"`-তে loop/`max` সাবধানে; এই বাস্তবায়নে `if cnt else 0` দিয়ে সামলানো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Task Scheduler** (