109 — Rearrange with Constraints¶

এই problem-এ greedy-র intuition একদম সিনেমার মতো — সবচেয়ে বড় বোঝাটা আগে নামাও। যে character সবচেয়ে বেশিবার আছে, সে-ই সবচেয়ে বড় হুমকি (পাশাপাশি বসে যাওয়ার), তাই তাকে আগে ফাঁকে ফাঁকে ছড়িয়ে দাও। ধীরে পড়ো; এখানে heap-এরও একটা ছোট teaser আছে (পুরো heap পরে আসবে)।

Source¶

Original source: LeetCode — Reorganize String
Platform: LeetCode — https://leetcode.com/problems/reorganize-string/
Topic: Greedy math tricks → most frequent first, feasibility bound
Difficulty: Medium
Pattern: most frequent first (সবচেয়ে frequent character আগে ছড়াও)
Basic idea inherited from: — (frequency-greedy-র প্রথম উদাহরণ)

1. Problem in simple words¶

একটা string s দেওয়া আছে (যেমন "aab")। তুমি এর অক্ষরগুলো এমনভাবে সাজাও যাতে কোনো দুটো একই অক্ষর পাশাপাশি না থাকে।

যদি এমন সাজানো সম্ভব হয়, একটা valid সাজানো রূপ ফেরত দাও; সম্ভব না হলে খালি string "" ফেরত দাও।

উদাহরণ: "aab" → "aba" (সম্ভব); "aaab" → "" (অসম্ভব, তিনটা a-কে আলাদা করার মতো যথেষ্ট ফাঁক নেই)।

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, ...)। এতে একই অক্ষর কখনো পাশাপাশি পড়ে না।

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/-তে)।

4. Real-life analogy¶

ভাবো তুমি একটা লম্বা টেবিলে অতিথিদের বসাচ্ছ, আর নিয়ম — একই পরিবারের দুজন পাশাপাশি বসবে না (যাতে তারা শুধু নিজেদের মধ্যে গল্প না করে)।

সবচেয়ে বড় পরিবারটাই সবচেয়ে বড় সমস্যা — তাদের যদি শেষে বসাও, ফাঁক পাবে না, দুজন পাশাপাশি পড়ে যাবে। তাই বড় পরিবারটাকে আগে, এক চেয়ার পর পর ছড়িয়ে বসাও (চেয়ার 0, 2, 4...)। তারপর বাকি ছোট পরিবারদের মাঝের ফাঁকা চেয়ারে। আর যদি একটা পরিবারই অর্ধেকের বেশি লোক হয়, তাহলে যত চালাকিই করো, দুজন পাশাপাশি পড়বেই — তখন সাজানো অসম্ভব।

5. Visual explanation¶

s = "aaabbc" (n = 6, a:3, b:2, c:1) — most frequent আগে, even index-এ:

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:

n = 4 → সর্বোচ্চ আলাদা রাখা যায়: _ X _ X  বা  X _ X _
        মানে একটা অক্ষর সর্বোচ্চ 2 বার = (4+1)//2

"aaab": a = 3 > 2  →  3টা a-কে আলাদা রাখার ফাঁক নেই → অসম্ভব

6. Example input and output¶

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 রূপ গ্রহণ করি।

7. Brute force thinking¶

সরাসরি, কিন্তু ধীর চিন্তা — সব permutation চেষ্টা করো, প্রতিটার মধ্যে দেখো কোনো দুটো পাশাপাশি অক্ষর সমান কিনা; প্রথম যেটা valid সেটাই ফেরত দাও:

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-এ কোটি ছাড়িয়ে যায় — সম্পূর্ণ অসম্ভব।

সব 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-এ বসানো:

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-এ নামায়।

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-এ বসেছে, তাই নিরাপদ।

12. Python solution¶

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¶

cnt = Counter(s)
max_freq = max(cnt.values()) if cnt else 0
if max_freq > (n + 1) // 2:
    return ""

প্রতিটা অক্ষরের গণনা বের করি; সবচেয়ে বেশি গণনা যদি (n+1)//2 ছাড়ায়, সাজানোই অসম্ভব — সঙ্গে সঙ্গে ""।

res = [None] * n
i = 0
for ch, f in cnt.most_common():

ফলাফলের জন্য n ঘরের একটা তালিকা; most_common() অক্ষরগুলো frequency-র অবরোহী ক্রমে দেয় — সবচেয়ে বড় হুমকি আগে।

        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-এর সাথে মেলায়।

14. Output walkthrough¶

চালালে ছাপবে (একটা সম্ভাব্য রূপ — placement নিয়ম fixed বলে এই বাস্তবায়নে নির্দিষ্ট):

aba
            <- এই লাইন আসলে খালি string (অসম্ভব)
abab
সব test pass!

প্রথম line "aab" → "aba"; দ্বিতীয় print খালি string ছাপে ("aaab" অসম্ভব, তাই ফাঁকা লাইন); তৃতীয় "aabb" → "abab"। তার আগে সব assert (feasibility + validity + ছোট সব string-এ brute মিলিয়ে) চুপচাপ pass করেছে, তাই শেষে সব test pass!।

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 দিয়ে সামলানো।

18. Harder problems that inherit this idea¶

LeetCode — Task Scheduler (https://leetcode.com/problems/task-scheduler/) — একই "most frequent first" greedy, এবার cooldown gap সহ; frequency bound-এর অসাধারণ প্রয়োগ।
LeetCode — Distant Barcodes (https://leetcode.com/problems/distant-barcodes/) — হুবহু reorganize, শুধু সংখ্যা দিয়ে — একই even/odd placement।
LeetCode — Reorganize String (https://leetcode.com/problems/reorganize-string/) — মূল problem; max-heap দিয়ে dynamic "সবচেয়ে frequent কে" সমাধান করলে heap-এর পূর্ণ রূপ দেখা যায়।

19. Pattern learned¶

Most frequent first (frequency greedy + feasibility bound) — সবচেয়ে বড় বোঝা (সর্বোচ্চ frequency) আগে ছড়িয়ে দাও; আর গণিতের সীমা ((n+1)//2) দিয়ে আগেই feasibility ঠিক করো। বড় শিক্ষা: "পাশাপাশি একই জিনিস নয়" ধরনের problem-এ সবচেয়ে বেশি-থাকা জিনিসটাই আসল হুমকি — তাকে আগে সামলাও।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "Reorganize string = most frequent first; count-এর max > (n+1)//2 হলে অসম্ভব (""), নাহলে সবচেয়ে frequent অক্ষর আগে even index-এ, পরে odd index-এ বসাও। dynamic দরকার হলে max-heap।"

পরের ধাপ → 110 — Maximum Product by Splitting (math greedy — যত পারো 3 ভাঙো)।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

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