Palindrome Partitioning Using Backtracking in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a substring is a palindrome.

DSA Python

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

Drag options to blanks, or click blank then click option'

A::-1

B::1

C::

D:-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using + or * instead of slicing to reverse the string.

Forgetting to reverse the string before comparison.

The slice s[::-1] reverses the string s. Comparing s with its reverse checks if it is a palindrome. The step -1 means traverse backwards.

2fill in blank

medium

Complete the code to add a partition to the current path.

DSA Python

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

Drag options to blanks, or click blank then click option'

Ainsert

Bextend

Cappend

Dremove

Attempts:

3 left

💡 Hint

Common Mistakes

Using extend which expects an iterable and would add characters separately.

Using remove which deletes elements instead of adding.

We use append to add the current palindrome substring to the path list.

3fill in blank

hard

Fix the error in the backtracking function call to avoid infinite recursion.

DSA Python

def backtrack(start, path):
    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([1], path)
            path.pop()

Drag options to blanks, or click blank then click option'

Astart

Blen(s)

C0

Dend

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same start index causing infinite recursion.

Using 0 or len(s) incorrectly as start index.

We must call backtrack with end as the new start index to move forward and avoid infinite loops.

4fill in blank

hard

Fill both blanks to create the palindrome partitioning function and initialize variables.

DSA Python

def partition(s):
    global result
    result = []
    def backtrack([1], path):
        if [2] == 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(end, path)
                path.pop()
    backtrack(0, [])
    return result

Drag options to blanks, or click blank then click option'

Astart

Bend

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'end' as the parameter name which is confusing.

Mismatching parameter names causing errors.

The function backtrack uses start as the index to track the current position in the string.

5fill in blank

hard

Fill both blanks to complete the palindrome partitioning solution with backtracking.

DSA Python

def partition(s):
    result = []
    def is_palindrome(sub):
        return sub == sub[::-1]
    def backtrack([1], path):
        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(end, path)
                path.pop()
    backtrack(0, [])
    return result

Drag options to blanks, or click blank then click option'

Bstart

Cend

Dstop

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect variable names for parameters.

Not reversing the substring correctly.

The palindrome check uses slicing with [::-1] to reverse the substring. The backtrack function uses start as the current index and end to move forward.

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