Skip to content

011 — Reorganize String

Source

  • Original source: Classic heap + greedy (most-frequent-first) arrangement
  • Platform: LeetCode — https://leetcode.com/problems/reorganize-string/
  • Topic: heap / priority queue
  • Difficulty: Medium
  • Pattern: Heap + greedy (সবচেয়ে frequent character আগে বসাও)
  • Basic idea inherited from: 05-hashing counting — frequency map; তারপর 08-এর max-heap-via-negation

1. Problem in simple words

একটা string s দেওয়া। তোমাকে এর character গুলো এমনভাবে rearrange করতে হবে যাতে পাশাপাশি দুটো একই character না থাকে। যদি এমন একটা arrangement সম্ভব হয়, সেটা return করো; সম্ভব না হলে empty string "" return করো।

s = "aab"   ->  "aba"   (পাশাপাশি কোনো 'a' নেই)
s = "aaab"  ->  ""      (অসম্ভব — 'a' বেশি)

2. Which basic idea does this inherit from?

ভিত দুটো। প্রথমে 05-hashing-এর frequency counting — কোন character কতবার আছে গুনে নাও। তারপর 08-এর max-heap-via-negation — প্রতিবার "এখন সবচেয়ে বেশি বাকি আছে কোন character?" সেটা দ্রুত পেতে। এই দুটো একসাথে জুড়লেই greedy arrangement দাঁড়িয়ে যায়।

3. What is the hidden math or logic?

লুকানো logic একটা feasibility শর্ত আর একটা greedy invariant। Feasibility: সবচেয়ে frequent character-এর count যদি (n + 1) // 2-এর বেশি হয়, তাহলে কোনোভাবেই আলাদা করে বসানো যায় না — তাই সরাসরি ""। Greedy: যতক্ষণ সম্ভব, এই মুহূর্তের সবচেয়ে frequent character বসাও, কিন্তু আগেরবার যেটা বসিয়েছ সেটাকে এক step hold করে রাখো যাতে পরপর একই না পড়ে।

4. Which data structure is needed?

একটা max-heap (count অনুযায়ী), সাথে একটা frequency dictionary। heapq min-heap বলে আমরা count-গুলো negate করে heap-এ রাখি — সবচেয়ে negative মানে সবচেয়ে বড় count।

5. Why this data structure fits

প্রতি step-এ তোমার দরকার শুধু সবচেয়ে frequent বাকি character — পুরো sorted order না। Heap ঠিক সেটাই O(log k)-এ দেয় (k = distinct character সংখ্যা)। আর একটা character বসানোর পরে তার count কমে; সেটা আবার heap-এ ফেরত গেলে O(log k)-এই ঠিক জায়গায় বসে।

6. Real-life analogy

ভাবো তুমি একটা প্লেটে রঙিন marble সাজাচ্ছ, নিয়ম — পাশাপাশি দুটো একই রঙ চলবে না। যেটার stock সবচেয়ে বেশি সেটাই আগে ফুরাতে চাও, কিন্তু একটা রাখার পর সেটাকে এক চাল বিরতি দাও, এর মধ্যে অন্য রঙ বসাও, তারপর আবার ফেরত আনো। "সবচেয়ে বেশি stock কোনটা" — সেই উত্তর চটজলদি দেয় heap।

7. Visual explanation

s = "aaabc" দিয়ে দেখি (max-heap-এ top = সবচেয়ে বড় count):

counts:  a=3, b=1, c=1     ->  max-heap top = a(3)
n = 5,  limit = (5+1)//2 = 3,   a=3 <= 3  ->  সম্ভব

বসাও a -> result "a"      hold a(left 2)
বসাও b -> result "ab"     a ফেরত,  hold b(left 0 -> বাদ)
বসাও a -> result "aba"    a(left 1) hold,  হাতে আর কেউ নেই tie তে...
বসাও c -> result "abac"   a ফেরত,  hold c(0 -> বাদ)
বসাও a -> result "abaca"  a(left 0 -> বাদ)

final: "abaca"  (পাশাপাশি কোনো জোড়া নেই)

8. Example input and output

Input : s = "aab"     -> Output: "aba"        (valid arrangement)
Input : s = "aaab"    -> Output: ""           (অসম্ভব)
Input : s = "a"       -> Output: "a"          (একটাই character)
Input : s = "aaabc"   -> Output: "abaca"      (অনেক valid; একটা দিলেই হলো)

9. Brute force thinking

প্রথম সরল চিন্তা: সব permutation generate করো, প্রতিটা check করো পাশাপাশি জোড়া আছে কিনা, প্রথম valid টা return করো।

"aab" -> "aab","aba","baa",...  -> "aba" প্রথম valid -> return

10. Why brute force is slow

n character-এর permutation সংখ্যা O(n!) — n একটু বড় হলেই এটা মহাকাশে চলে যায়। অথচ আমাদের সব permutation দরকার নেই; একটা valid arrangement greedy ভাবেই বানানো যায়। তাই factorial খাটুনি নিখাদ অপচয়।

11. Key observation

মূল observation: যদি বারবার এই মুহূর্তের সবচেয়ে frequent (কিন্তু আগেরবার বসানোটা ছাড়া) character বসাই, পরপর duplicate কখনোই পড়বে না — যদি না একটা character এত বেশি যে feasibility ভেঙে যায়। আর সেই feasibility এক লাইনে ধরা যায়: max_count <= (n + 1) // 2।

12. Optimized intuition

Count নাও, max-heap-এ ঢালো (negate করা count)। একটা "previous" slot রাখো (গতবার বসানো character, তার বাকি count)। Loop: top pop করো, result-এ যোগ করো, তার count এক কমাও; আগের previous-এর count > 0 হলে এখন তাকে heap-এ ফেরত দাও; এই বসানোটাকে নতুন previous বানাও। শেষে result-এর length মূল string-এর সমান হলে valid, নাহলে ""।

13. Thinking tweak

মোচড়: "string সাজানো" না ভেবে ভাবো "একটা changing multiset থেকে বারবার max টানছি, কিন্তু একটা item-কে এক চাল cooldown-এ রাখছি।" "পাশাপাশি একই নয় / প্রতি k-distance-এ একবার" — এমন কথা শুনলেই heap + একটা delay/cooldown bucket-এর কথা মাথায় আসা উচিত (Task Scheduler-এর সাথে যমজ)।

14. Step-by-step dry run

Input s = "aab":

  1. counts → a=2, b=1; n=2, limit=(2+1)//2=1... দাঁড়াও, n=3 (string length 3), limit=(3+1)//2=2, a=2 ≤ 2 → সম্ভব
  2. heap = {a:2, b:1} (negate করা), prev = None
  3. pop a → result "a", a-left=1; prev ছিল None, কিছু ফেরত না; prev=(a,1)
  4. pop b → result "ab", b-left=0; prev=(a,1) আছে → a ফেরত heap-এ; prev=(b,0)
  5. pop a → result "aba", a-left=0; prev=(b,0) count 0 → ফেরত না; prev=(a,0)
  6. heap খালি, loop শেষ → len("aba")==3 → return "aba"

15. Python solution

import heapq
from collections import Counter

def reorganize_string(s):
    counts = Counter(s)
    n = len(s)
    # feasibility: সবচেয়ে frequent character (n+1)//2-এর বেশি হলে অসম্ভব
    if max(counts.values(), default=0) > (n + 1) // 2:
        return ""

    heap = [(-cnt, ch) for ch, cnt in counts.items()]
    heapq.heapify(heap)             # top = সবচেয়ে বেশি বাকি character

    result = []
    prev = None                     # (remaining_count, ch) — এক চাল cooldown
    while heap:
        cnt, ch = heapq.heappop(heap)   # cnt negative; সবচেয়ে frequent
        result.append(ch)
        # আগের character cooldown শেষ — এখন তাকে heap-এ ফেরত দাও
        if prev and prev[0] < 0:
            heapq.heappush(heap, prev)
        prev = (cnt + 1, ch)            # count এক কমালাম (negative বলে +1)

    out = "".join(result)
    return out if len(out) == n else ""

def _no_adjacent_dup(t):
    return all(t[i] != t[i + 1] for i in range(len(t) - 1))

# ---- tests ----
r1 = reorganize_string("aab")
assert r1 != "" and sorted(r1) == sorted("aab") and _no_adjacent_dup(r1)

assert reorganize_string("aaab") == ""        # অসম্ভব

assert reorganize_string("a") == "a"          # একটাই character

r2 = reorganize_string("aaabc")
assert r2 != "" and sorted(r2) == sorted("aaabc") and _no_adjacent_dup(r2)

r3 = reorganize_string("vvvlo")
assert r3 != "" and sorted(r3) == sorted("vvvlo") and _no_adjacent_dup(r3)

assert reorganize_string("") == ""            # খালি string

print("সব test pass!")

16. Line-by-line code explanation

  • counts = Counter(s) — প্রতিটা character কতবার আছে গুনে নেয় (05-hashing-এর frequency map)।
  • if max(...) > (n + 1) // 2: return "" — feasibility guard; একটা character এত বেশি হলে আলাদা করা অসম্ভব।
  • heap = [(-cnt, ch) ...]; heapify — negate করা count-এর max-heap; top = সবচেয়ে frequent।
  • prev = None — এক চাল আগে বসানো character, যাতে পরপর duplicate না পড়ে।
  • cnt, ch = heappop(...) — এই মুহূর্তের সবচেয়ে frequent; cnt negative।
  • if prev and prev[0] < 0: heappush(heap, prev) — আগেরটার cooldown শেষ, count বাকি থাকলে ফেরত।
  • prev = (cnt + 1, ch) — বসানো character-এর count এক কমিয়ে cooldown-এ রাখা (negative বলে +1)।
  • return out if len(out) == n else "" — সব character বসাতে পারলে valid, নাহলে ""।

17. Output walkthrough

reorganize_string("aab") section 14-এর dry run মেনে "aba" ধাঁচের একটা valid string দেয় — test শুধু "জোড়া নেই + একই multiset" যাচাই করে (order unspecified)। "aaab" feasibility-তেই আটকে ""; "a" সরাসরি "a"; "" খালি বলে ""। সব assert pass-এর পরে print হয়: সব test pass!।

18. Time complexity

O(n log k) — n = string length, k = distinct character সংখ্যা। প্রতিটা character একবার pop আর একবার push হয়, প্রতিটা O(log k)। Counting O(n)। ছোট alphabet-এ k ≤ 26 বলে কার্যত O(n)।

19. Space complexity

O(n + k) — result string O(n), heap আর counter O(k)। ছোট alphabet-এ heap/counter constant, তাই dominant অংশ result-ই।

20. Common mistakes

  • feasibility guard ভুলে যাওয়া — তখন অসম্ভব input-এও ভুলভাবে কিছু একটা ফেরত দিতে পারো।
  • previous character তখনই ফেরত না দেওয়া (পরের iteration-এ) — তখন একই character পরপর বসে যায়।
  • count কমানোর সময় sign ভুল করা — negative count, তাই "এক কমানো" মানে cnt + 1, cnt - 1 নয়।
  • শেষে length check না করা — কিছু edge case-এ heap শূন্য হয়েও সব character বসে না; তখন "" দরকার।

21. Which basic problem this inherits from

ভিত্তি 05-hashing-এর frequency counting (Counter) আর 08-এর concept.md-র max-heap-via-negation। আর patterns.md-র Pattern 6 (Heap + greedy combos) — "সবসময় most frequent next নাও" — এর সরাসরি প্রয়োগ, একটা cooldown twist সহ।

22. Similar harder problems

23. Pattern learned

Heap + greedy with cooldown: সবচেয়ে frequent item বারবার নাও, কিন্তু গতবার নেওয়াটাকে এক (বা k) চাল hold করে রাখো। greedy ঠিক করে কোনটা — heap সেটা O(log k)-এ দেয়, আর একটা "previous/cooldown" slot adjacency নিয়ম রক্ষা করে।

24. Final summary

ভবিষ্যতের আমাকে: "পাশাপাশি একই নয় / সবচেয়ে frequent আগে" = max-heap + একটা previous-slot cooldown। প্রথমে feasibility (max_count <= (n+1)//2) check করবে, তারপর greedy loop। এটা Task Scheduler-এরই ছোট ভাই — একটাকে পারলে অন্যটাও প্রায় চোখ বন্ধ করে লেখা চাই।

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