Palindrome Partitioning Using Backtracking in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Palindrome Partitioning for 'aab'

What is the output of the following code that finds all palindrome partitions of the string 'aab'?

DSA Python

def is_palindrome(s):
    return s == s[::-1]

def backtrack(s, start, path, result):
    if start == len(s):
        result.append(path[:])
        return
    for end in range(start + 1, len(s) + 1):
        if is_palindrome(s[start:end]):
            path.append(s[start:end])
            backtrack(s, end, path, result)
            path.pop()

result = []
backtrack('aab', 0, [], result)
print(result)

A [['a', 'ab'], ['aa', 'b']]

B [['a', 'a', 'b'], ['aa', 'b']]

C [['a', 'a', 'b']]

D [['aa', 'b'], ['a', 'a']]

💡 Hint

Check all substrings and only add those which are palindromes.

The code finds all partitions where each substring is a palindrome. For 'aab', the partitions are ['a', 'a', 'b'] and ['aa', 'b'].

🧠 Conceptual

intermediate

Number of Palindrome Partitions for 'racecar'

How many palindrome partitions does the string 'racecar' have?

A 10

B 8

C 6

D 4

💡 Hint

Consider all ways to split 'racecar' into palindromic substrings.

The string 'racecar' has 4 palindrome partitions: ['r','a','c','e','c','a','r'], ['r','a','cec','a','r'], ['r','aceca','r'], ['racecar'].

🔧 Debug

advanced

Identify the Error in Palindrome Partitioning Code

What error does the following code produce when run?

DSA Python

def is_palindrome(s):
    return s == s[::-1]

def backtrack(s, start, path, result):
    if start == len(s):
        result.append(path)
        return
    for end in range(start + 1, len(s) + 1):
        if is_palindrome(s[start:end]):
            path.append(s[start:end])
            backtrack(s, end, path, result)
            path.pop()

result = []
backtrack('aba', 0, [], result)
print(result)

A The output contains duplicate references causing unexpected results

B [['a', 'b', 'a'], ['aba'], ['a', 'b', 'a']]

C [['a', 'b', 'a'], ['aba'], ['a', 'b', 'a'], ['aba']]

D [['a', 'b', 'a'], ['aba']]

💡 Hint

Check how the path list is appended to result.

Appending 'path' directly adds a reference, so all entries in result point to the same list, causing duplicates or unexpected results.

🚀 Application

advanced

Find All Palindrome Partitions of 'level'

Which option correctly lists all palindrome partitions of the string 'level'?

A [['l', 'e', 'v', 'e', 'l'], ['l', 'eve', 'l'], ['level']]

B [['l', 'e', 'v', 'e', 'l'], ['le', 'v', 'el'], ['level']]

C [['l', 'e', 'v', 'e', 'l'], ['l', 'eve', 'l'], ['le', 'vel']]

D [['l', 'e', 'v', 'e', 'l'], ['l', 'eve'], ['level']]

💡 Hint

Check which substrings are palindromes.

Only 'l', 'e', 'v', 'eve', and 'level' are palindromes in the string 'level'.

📝 Syntax

expert

Identify Syntax Error in Palindrome Partitioning Code

Which option contains a syntax error in the palindrome partitioning backtracking code?

A

for end in range(start + 1, len(s) + 1):
    if is_palindrome(s[start:end]):
        path.append(s[start:end])
        backtrack(s, end, path, result)
        path.pop()

B

)(pop.htap        
)tluser ,htap ,dne ,s(kcartkcab        
)]dne:trats[s(dneppa.htap        
:)]dne:trats[s(emordnilap_si fi    
:)1 + )s(nel ,1 + trats(egnar ni dne rof

C

for end in range(start + 1, len(s) + 1)
    if is_palindrome(s[start:end]):
        path.append(s[start:end])
        backtrack(s, end, path, result)
        path.pop()

D

or end in range(start + 1, len(s) + 1):
    if is_palindrome(s[start:end]):
        path.append(s[start:end])
        backtrack(s, end, path, result)
        path.pop()

💡 Hint

Check for missing colons in for loops.

Option C is missing a colon ':' at the end of the for loop line, causing a syntax error.

Practice

1. What is the main goal of palindrome partitioning using backtracking on a string s?

easy

A. To split s into all possible substrings where each substring is a palindrome

B. To find the longest palindrome substring in s

C. To count the total number of palindromes in s

D. To reverse the string s and check if it is a palindrome

Solution

1. Step 1: Understand palindrome partitioning

   Palindrome partitioning means dividing the string into parts where each part reads the same forwards and backwards.

2. Step 2: Role of backtracking

   Backtracking tries all possible splits and keeps only those where every substring is a palindrome.

3. Final Answer:

   To split s into all possible substrings where each substring is a palindrome -> Option A

4. Quick Check:

   Palindrome partitioning = all palindrome substrings [OK]

Hint: Backtracking tries all splits keeping palindrome parts [OK]

Common Mistakes:

• Confusing palindrome partitioning with longest palindrome substring
• Thinking it counts palindromes instead of listing partitions
• Assuming it just reverses the string

2. Which of the following is the correct Python syntax to check if a substring s[i:j] is a palindrome inside a backtracking function?

easy

A. if s[i:j] == s[j:i]:

B. if s[i:j] == reversed(s[i:j]):

C. if s[i:j] == s[i:j][::-1]:

D. if s[i:j] == s[j:i][::-1]:

Solution

1. Step 1: Understand Python slicing and reversal

   Using s[i:j][::-1] reverses the substring from index i to j-1.

2. Step 2: Compare substring with its reverse

   If s[i:j] equals its reversed version, it is a palindrome.

3. Final Answer:

   if s[i:j] == s[i:j][::-1]: -> Option C

4. Quick Check:

   Substring == reversed substring [OK]

Hint: Use slicing with [::-1] to reverse substring [OK]

Common Mistakes:

• Using reversed() which returns an iterator, not a string
• Comparing s[i:j] with s[j:i] which is empty or invalid
• Incorrect slicing order causing empty strings

3. What will be the output of the following code snippet?

def backtrack(s, start, path, result):
    if start == len(s):
        result.append(path[:])
        return
    for end in range(start + 1, len(s) + 1):
        if s[start:end] == s[start:end][::-1]:
            path.append(s[start:end])
            backtrack(s, end, path, result)
            path.pop()

result = []
backtrack('aab', 0, [], result)
print(result)

medium

A. [['a', 'a', 'b'], ['aa', 'b']]

B. [['a', 'ab'], ['aa', 'b']]

C. [['a', 'a', 'b']]

D. [['aa', 'ab']]

Solution

1. Step 1: Trace backtracking on 'aab'

   Partitions found are ['a','a','b'] and ['aa','b'] because 'a', 'aa', and 'b' are palindromes.

2. Step 2: Confirm all palindrome partitions collected

   Both partitions are added to result list before printing.

3. Final Answer:

   [['a', 'a', 'b'], ['aa', 'b']] -> Option A

4. Quick Check:

   All palindrome partitions = [['a', 'a', 'b'], ['aa', 'b']] [OK]

Hint: Check all palindrome splits recursively [OK]

Common Mistakes:

• Missing the partition ['aa', 'b']
• Including non-palindrome substrings like 'ab'
• Not popping path after recursion causing wrong results

4. Identify the error in the following backtracking code for palindrome partitioning:

def backtrack(s, start, path, result):
    if start == len(s):
        result.append(path)
        return
    for end in range(start + 1, len(s) + 1):
        if s[start:end] == s[start:end][::-1]:
            path.append(s[start:end])
            backtrack(s, end, path, result)
            path.pop()

result = []
backtrack('aba', 0, [], result)
print(result)

medium

A. The loop range should start from start, not start + 1

B. The palindrome check is incorrect

C. Missing return statement after appending to result

D. Appending path directly causes all results to be the same list

Solution

1. Step 1: Understand list reference behavior in Python

   Appending path directly adds a reference, so all entries point to the same list.

2. Step 2: Fix by appending a copy of path

   Use result.append(path[:]) to save a snapshot of current path.

3. Final Answer:

   Appending path directly causes all results to be the same list -> Option D

4. Quick Check:

   Append copy of path, not path itself [OK]

Hint: Always append a copy of path to result [OK]

Common Mistakes:

• Appending the same list reference causing duplicate results
• Incorrect palindrome check logic
• Wrong loop range causing missed substrings

5. Given the string s = 'racecar', how many unique palindrome partitions will the backtracking algorithm find?

hard

A. 4

B. 8

C. 6

D. 10

Solution

1. Step 1: List all palindrome partitions of 'racecar'

   Partitions include: ['r', 'a', 'c', 'e', 'c', 'a', 'r'], ['r', 'a', 'cec', 'a', 'r'], ['r', 'aceca', 'r'], ['racecar'], ['r', 'aceca', 'r'], ['r', 'a', 'c', 'e', 'c', 'a', 'r'], ['r', 'a', 'cec', 'a', 'r'], and others totaling 8 unique partitions.

2. Step 2: Confirm count by backtracking logic

   Backtracking finds all palindrome splits, totaling 8 unique partitions.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   Unique palindrome partitions count = 8 [OK]

Hint: Count all palindrome splits carefully [OK]

Common Mistakes:

• Counting non-palindrome substrings as partitions
• Missing longer palindrome substrings like 'aceca'
• Assuming only single-character partitions