কনটেন্টে যান

016 — Palindrome Partitioning

Problem link ও উৎস

  • Original source: Classic backtracking exercise (partition into palindromes)
  • Platform: LeetCode — https://leetcode.com/problems/palindrome-partitioning/
  • Topic: recursion / backtracking (cut-point backtracking)
  • Difficulty: Medium
  • Pattern: cut-point backtracking — প্রতি cut-এ palindrome হলে এগোও, নাহলে বাদ
  • Basic idea inherited from: Combinations (cut position-গুলোই choice)

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

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

একটা string s দেওয়া আছে। তোমার কাজ: একে এমনভাবে টুকরো করা (partition করা) যেন প্রতিটা টুকরোই palindrome (উল্টে পড়লেও একই) — আর এমন সব সম্ভাব্য টুকরো-করা বের করা। মূল string-এর অক্ষর-ক্রম বদলায় না, শুধু কোথায় কোথায় "কাটছ" সেটাই পছন্দ। প্রতিটা partition একটা টুকরোর তালিকা।

উদাহরণ
s = "aab"
partitions = ["a","a","b"], ["aa","b"]   ("aab" নিজে palindrome নয়, তাই পুরোটা এক টুকরো হয় না)

Input ও output

উদাহরণ
Input : "aab" -> Output: ["a","a","b"], ["aa","b"]
Input : "aba" -> Output: ["a","b","a"], ["aba"]

Edge case 1 (এক অক্ষর): "a"  -> Output: [["a"]]
Edge case 2 (সব সমান):  "aa" -> Output: ["a","a"], ["aa"]

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

একটা লম্বা পুঁতির মালা ভাবো, যেটা তুমি কয়েক টুকরোয় কাটতে চাও — কিন্তু শর্ত: প্রতিটা টুকরোর পুঁতির নকশা দুদিক থেকে একই রকম (symmetric) হতে হবে। তুমি বাঁ-প্রান্ত থেকে শুরু করে একটা symmetric টুকরো কাটো, তারপর বাকি মালার জন্য একই কাজ করো। সব রকম বৈধ কাটাই হলো সব partition।

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

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

ভিত্তি হলো Combinations — cut position-গুলোই choice। Combinations-এ আমরা index বাছতাম; এখানে বাছি কোথায় কাটব। একটা start position থেকে প্রতিটা সম্ভাব্য শেষ position পর্যন্ত একটা টুকরো ভাবি; টুকরোটা palindrome হলে সেটা নিয়ে বাকি string-এর জন্য recurse করি (start = ওই টুকরোর পরে)। start-index দিয়ে সবসময় সামনে এগোনো — combinations-এর সেই কঙ্কাল, এখন cut-point-এর ভাষায়।

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

লুকানো logic হলো n-অক্ষরের string-এ n-1টা সম্ভাব্য cut-গাপ, প্রতিটায় কাটা/না-কাটা দুই পছন্দ — মানে সর্বোচ্চ 2^(n-1) রকম partition। কিন্তু palindrome শর্ত বেশিরভাগ partition বাতিল করে (validity pruning)। প্রতিটা recursive call একটা বৈধ palindrome prefix নেয়, তারপর "বাকি suffix কীভাবে partition হবে" — একই সমস্যা, ছোট string-এ।

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

একটা list path (বর্তমান partition-এর টুকরোগুলো), একটা list out (সব partition জমাতে), একটা integer start (পরবর্তী টুকরো কোথা থেকে), একটা palindrome-check helper, আর recursion-এর জন্য call stack। record-এ path[:] snapshot।

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

start integer-টা বলে দেয় suffix কোথা থেকে শুরু — তাই প্রতিটা partition বাঁ-থেকে-ডান একটাই ক্রমে গড়ে, পুনরাবৃত্তি নেই (combinations-এর start-index ভূমিকা)। path mutable বলে টুকরো append/pop O(1)। palindrome-check sub == sub[::-1] সরল ও O(length); চাইলে এটাকে precompute (DP table) দিয়ে দ্রুত করা যায় — সেটাই memoization → DP-র দিকে ইশারা।

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

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

প্রথম সরল চিন্তা: n-1টা cut-গাপের প্রতিটায় কাটা/না-কাটা — সব 2^(n-1) রকম partition গড়ো, তারপর যে partition-এর সব টুকরো palindrome শুধু সেগুলো রাখো।

উদাহরণ
for each subset of cut positions (2^(n-1)):
    pieces = split s at those cuts
    if all(p == p[::-1] for p in pieces):
        out.append(pieces)

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

এই version সবসময় পুরো 2^(n-1)টা partition গড়ে, তারপর প্রতিটার প্রতিটা টুকরো palindrome কিনা যাচাই করে — অধিকাংশই প্রথম non-palindrome টুকরোতেই বাতিল, কিন্তু গড়া হয়ে যাওয়ার পরে। অপচয়: একটা prefix অলরেডি non-palindrome জানা সত্ত্বেও তার পরের সব cut-সমন্বয় গড়া হয়। backtracking যে মুহূর্তে একটা টুকরো non-palindrome, সেই branch-এ আর নামেই না — তাই hopeless subtree গাছেই কাটা পড়ে।

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

মূল observation: প্রতিটা সিদ্ধান্ত হলো "পরের টুকরো কোথায় শেষ হবে", আর সেই টুকরো palindrome হলে তবেই বৈধ branch। "সব partition কী?" না ভেবে ভাবো "এই start থেকে একটা বৈধ (palindrome) prefix কতদূর হতে পারে?" — প্রতিটা বৈধ prefix-এর জন্য বাকি suffix recursively partition হয়। validity-টা branch খোলার শর্ত, শেষের test নয়।

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

go(start, path): base case start == len(s) হলে snapshot record (পুরো string ঢাকা পড়েছে)। নাহলে end start+1 থেকে len(s) পর্যন্ত: piece = s[start:end]; যদি piece palindrome হয় → append (choose), go(end, path) (explore — পরের টুকরো end থেকে), pop (un-choose)। palindrome না হলে সেই end skip। start-index combinations + প্রতি cut-এ validity গেট।

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

মোচড়: "কোথায় কোথায় কাটব" — সব cut একসাথে ভেবো না; ভাবো "এই বাঁ-প্রান্ত থেকে একটা বৈধ palindrome টুকরো নিই, বাকিটা recursion সামলাক।" বড় partition-সমস্যাটা নেমে আসে "এক টুকরো বাছো, ছোট string-এ একই সমস্যা"-তে — Combinations-এর "এক item বাছো, এগোও"-এর হুবহু রূপ, শুধু item-এর জায়গায় palindrome prefix।

ছবিতে বোঝা

start থেকে প্রতিটা end চেষ্টা; piece palindrome হলেই recurse। "aab"-এর tree:

উদাহরণ
                         go(0, [])
        "a"(pal) /        "aa"(pal) |        "aab"(না-pal, বাদ)
   go(1, ["a"])        go(2, ["aa"])
   "a"(pal)|            "b"(pal)|
   go(2,["a","a"])     go(3,["aa","b"]) -> record ["aa","b"]
   "b"(pal)|
   go(3,["a","a","b"]) -> record ["a","a","b"]

start == len(s) -> record; piece palindrome না হলে সেই branch বাদ।

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

partition("aab"), go(start, path):

  1. go(0,[]): end=1 "a" (pal): append → go(1,["a"])।
  2. go(1,["a"]): end=2 "a" (pal): append → go(2,["a","a"])।
  3. go(2,["a","a"]): end=3 "b" (pal): append → go(3,["a","a","b"]): start==3 → record ["a","a","b"]; pop চেইন।
  4. go(1,["a"]): end=3 "ab" (না-pal): skip; pop "a"।
  5. go(0,[]): end=2 "aa" (pal): append → go(2,["aa"]): end=3 "b" (pal): record ["aa","b"]। end=3 "aab" (না-pal): skip।
  6. out = [["a","a","b"], ["aa","b"]] — 2টা।

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

Python

Python
def partition(s):
    out = []
    def is_pal(sub):
        return sub == sub[::-1]       # উল্টো করে মিলিয়ে দেখা
    def go(start, path):
        if start == len(s):           # base case: পুরো string ঢাকা পড়েছে
            out.append(path[:])       # snapshot!
            return
        for end in range(start + 1, len(s) + 1):
            piece = s[start:end]
            if is_pal(piece):         # validity গেট
                path.append(piece)    # CHOOSE
                go(end, path)         # EXPLORE (পরের টুকরো end থেকে)
                path.pop()            # UN-CHOOSE
    go(0, [])
    return out

# ---- order-independent তুলনার helper (টুকরোর ক্রম জরুরি) ----
def norm(list_of_lists):
    return sorted(list_of_lists)      # শুধু বাইরের list sort, টুকরোর ক্রম অটুট

# ---- tests ----
assert norm(partition("aab")) == norm([["a", "a", "b"], ["aa", "b"]])
assert norm(partition("aba")) == norm([["a", "b", "a"], ["aba"]])
assert partition("a") == [["a"]]
assert norm(partition("aa")) == norm([["a", "a"], ["aa"]])
assert len(partition("aab")) == 2
assert all(all(p == p[::-1] for p in part) for part in partition("aabb"))  # সব টুকরো palindrome
print("সব test pass!")

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

  • def is_pal(sub): return sub == sub[::-1] — টুকরোটা palindrome কিনা; [::-1] উল্টো করে।
  • if start == len(s): — base case: পুরো string-ই টুকরোয় ঢাকা পড়েছে, একটা পূর্ণ partition।
  • out.append(path[:]) — snapshot; live path পরে বদলাবে।
  • for end in range(start+1, len(s)+1): — start থেকে প্রতিটা সম্ভাব্য টুকরো-শেষ (cut position)।
  • if is_pal(piece): — validity গেট: শুধু palindrome টুকরোর branch খোলো।
  • path.append(piece); go(end, path); path.pop() — choose → explore (পরের টুকরো end থেকে) → un-choose।

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

partition("aab"): start=0 থেকে "a" ও "aa" দুটোই palindrome, তাই দুটো শাখা; "aab" palindrome নয় বলে পুরোটা-একটুকরো branch বাদ। প্রথম শাখা ["a","a","b"], দ্বিতীয় ["aa","b"]। ফল 2টা। partition-এ টুকরোর ক্রম জরুরি (["a","a","b"] একটা sequence), তাই norm-এ শুধু বাইরের list sort করি (sorted-of-sorted নয়) — assert stable অথচ সঠিক। "a"-তে 1টা, আর সব টুকরো palindrome যাচাই। সব মিলে print: সব test pass!।

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

সময়

worst case O(n · 2^n) — সর্বোচ্চ 2^(n-1) partition (যেমন সব অক্ষর সমান), প্রতিটা গড়তে ও palindrome-check-এ O(n) পর্যন্ত। is-palindrome precompute করলে check অংশ O(1) করা যায়।

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

Output বাদ দিলে O(n) — call stack + path-এর গভীরতা n (প্রতি অক্ষর আলাদা টুকরো হলে)। Output ধরলে সব partition-এর মোট আকার।

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

  • palindrome-check বাদ দিয়ে সব cut গড়ে শেষে filter করা — hopeless branch-এ নেমে অপচয়; গেটটা branch খোলার আগে দাও।
  • go(end)-এর বদলে go(end+1) বা go(start+1) — হয় অক্ষর বাদ পড়ে, নয় টুকরো ঠিকমতো জোড়া লাগে না।
  • range(start+1, len(s)+1)-এর +1 ভুলে যাওয়া — শেষ অক্ষরের টুকরো বা শেষ end ধরা পড়ে না।
  • out.append(path) snapshot ছাড়া — সব entry একই live list-এর reference।

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

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

ভিত্তি: Combinations (এই tracker-এর #11)-এর start-index — এখানে "item" বদলে "palindrome prefix"। ../patterns.md-এর Pattern 5 (start-index) + Pattern 6 (validity গেট) দুটোর মিশ্রণ। এটা Word Search (#17) বা cut-ভিত্তিক DP (যেমন Palindrome Partitioning II — min cuts) এর দিকে সেতু — সেখানে count/min চাইলে memoize করে ../../12-dynamic-programming/।

পরের অনুশীলন

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

Cut-point backtracking: start position থেকে প্রতিটা সম্ভাব্য prefix-এ একটা validity গেট (এখানে palindrome) বসাও; বৈধ হলে prefix নিয়ে suffix-এ recurse করো (go(end)), নাহলে branch বাদ — string-কে বৈধ টুকরোয় ভাগ করার সব problem-এর কঙ্কাল।

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

ভবিষ্যতের আমাকে: "Palindrome Partitioning = start থেকে প্রতিটা end-এ piece বানাও; palindrome হলে নাও আর go(end); base case start==len(s)।" যখনই 'string-কে বৈধ টুকরোয় ভাগ করো' শুনবে — এই cut-point start-index skeleton মনে করবে; আর 'সর্বনিম্ন কয় কাট/কয়ভাবে' হলে memoize করে DP-তে যাও।

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