Skip to content

016 — Palindrome Partitioning

Source

  • 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)

1. Problem in simple words

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

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

2. Which basic idea does this inherit from?

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

3. What is the hidden math or logic?

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

4. Which data structure is needed?

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

5. Why this data structure fits

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-র দিকে ইশারা।

6. Real-life analogy

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

7. Visual explanation

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 বাদ।

8. Example input and 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"]

9. Brute force thinking

প্রথম সরল চিন্তা: 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)

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

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 গেট।

13. Thinking tweak

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

14. Step-by-step dry run

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টা।

15. Python solution

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

16. Line-by-line code explanation

  • 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।

17. Output walkthrough

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!।

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

  • 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।

21. Which basic problem this inherits from

ভিত্তি: 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/।

22. Similar harder problems

23. Pattern learned

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

24. Final summary

ভবিষ্যতের আমাকে: "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।