কনটেন্টে যান

011 — Reorganize String

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

  • 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

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

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

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

Input ও output

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

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

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

ভেতরের যুক্তি

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

কী দিয়ে তথ্য রাখব

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

এটি কেন উপযুক্ত

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

উদাহরণ
"aab"-এর distinct permutations: "aab", "aba", "baa"
"aab" অবৈধ (aa), "aba" বৈধ, "baa" অবৈধ (aa) -> "aba"

কোথায় বেশি কাজ হচ্ছে

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

যে বিষয়টি খেয়াল করতে হবে

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

আরও কম কাজে সমাধান

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

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

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; heap-এ c(left 1) বাকি
বসাও c -> result "abac"   a ফেরত,  hold c(0 -> বাদ)
বসাও a -> result "abaca"  a(left 0 -> বাদ)

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

ছোট input-এ ধাপে ধাপে

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"

কোড ও ব্যাখ্যা

Python

Python
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!")

কোডের প্রতিটি অংশ

  • 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, নাহলে ""।

Output মিলিয়ে দেখা

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

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "পাশাপাশি একই নয় / সবচেয়ে 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।