Palindrome Partitioning

📋

Palindrome Partitioning

Edge cases:

</>

IDE

def partition(s: str) -> list:public List<List<String>> partition(String s)vector<vector<string>> partition(string s)function partition(s)

def partition(s):
    # Write your solution here
    pass

class Solution {
    public List<List<String>> partition(String s) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
#include <string>
using namespace std;

vector<vector<string>> partition(string s) {
    // Write your solution here
    return {};
}

function partition(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [["a","b","b","a"]]Only returned one partition instead of all possible partitions.✅ Ensure backtracking explores all substring splits and collects all valid partitions, not just one.

Wrong: [["a","a","b"]]Missed longer palindrome substrings like 'aa'.✅ Check all substring lengths and include substrings that are palindromes, not just single characters.

Wrong: [["a","b","a","a","b","a"]]Greedy approach picking only smallest palindromes, missing longer nested palindromes.✅ Backtrack by exploring all substring lengths at each step, not just the smallest or largest.

Wrong: []Returned empty list for non-empty input due to missing base case or incorrect recursion.✅ Add base case to add current path to result when start index reaches string length.

Wrong: [["a","b","c"],["abc"]]Incorrect palindrome check allowing non-palindromic substrings like 'abc'.✅ Implement strict palindrome check function that returns false for non-palindromes.

✓

Test Cases

Make sure your solution handles empty and single character strings correctly before moving on.

Review your palindrome checking logic and ensure your backtracking explores all substring splits.

Consider memoization or dynamic programming to optimize palindrome checks and reduce recursion overhead.

t1_01basic

Input{"s":"aab"}

Expected[["a","a","b"],["aa","b"]]

⏱ Performance - must finish in 2000ms

The string 'aab' can be partitioned into palindromes as ['a','a','b'] and ['aa','b'].

💡 Try backtracking by choosing substrings and checking if they are palindromes.

💡 Use a helper function to check palindrome substrings efficiently.

💡 Add substrings to the current path only if they are palindromes, then recurse.

Why it failed: Failed to generate all palindrome partitions or missed 'aa' substring. Fix palindrome check and backtracking logic to include all valid partitions.

✓ Correctly generated all palindrome partitions for the canonical example.

t1_02basic

Input{"s":"racecar"}

Expected[["r","a","c","e","c","a","r"],["r","a","cec","a","r"],["r","aceca","r"],["racecar"]]

⏱ Performance - must finish in 2000ms

The string 'racecar' has multiple palindrome partitions including single letters and longer palindromes like 'cec', 'aceca', and 'racecar'.

💡 Consider all substrings and check palindrome property before recursing.

💡 Longer palindromes like 'racecar' and 'aceca' should be included as partitions.

💡 Backtracking must explore all splits, not just single characters.

Why it failed: Missed longer palindrome partitions like 'aceca' or 'racecar'. Ensure backtracking explores all substring lengths and palindrome checks.

✓ All palindrome partitions including longer palindromes correctly found.

t2_01edge

Input{"s":""}

Expected[[]]

⏱ Performance - must finish in 2000ms

Empty string has no partitions, so result is an empty list.

💡 Check if input string is empty before processing.

💡 Return empty list immediately if string length is zero.

💡 Avoid starting backtracking if string is empty.

Why it failed: Returned non-empty result for empty string input. Fix by adding base case to return [] when input is empty.

✓ Correctly handled empty string input with empty partition list.

t2_02edge

Input{"s":"z"}

Expected[["z"]]

⏱ Performance - must finish in 2000ms

Single character string 'z' has only one palindrome partition: itself.

💡 Single characters are always palindromes.

💡 Backtracking should return [[s]] when string length is 1.

💡 Ensure base case adds current path when start index reaches string length.

Why it failed: Failed to return single partition for single character input. Fix base case to add current path when start == len(s).

✓ Correctly returned single partition for single character string.

t2_03edge

Input{"s":"aaaa"}

Expected[["a","a","a","a"],["a","a","aa"],["a","aa","a"],["a","aaa"],["aa","a","a"],["aa","aa"],["aaa","a"],["aaaa"]]

⏱ Performance - must finish in 2000ms

String with all identical characters 'aaaa' has multiple palindrome partitions with varying substring lengths.

💡 All substrings of identical characters are palindromes.

💡 Backtracking must explore all substring lengths from 1 to n.

💡 Memoization can optimize repeated palindrome checks for identical chars.

Why it failed: Missed some partitions with longer palindrome substrings. Fix backtracking to explore all substring lengths, not just single chars.

✓ All palindrome partitions for identical characters correctly generated.

t2_04edge

Input{"s":"abc"}

Expected[["a","b","c"]]

⏱ Performance - must finish in 2000ms

String with no palindromic substrings longer than 1 results in partitions of single characters only.

💡 Check palindrome condition carefully; substrings longer than 1 may not be palindromes.

💡 Backtracking should not include non-palindromic substrings.

💡 Ensure palindrome check is correct and does not allow non-palindromes.

Why it failed: Incorrectly included non-palindromic substrings like 'ab' or 'bc'. Fix palindrome check to strictly verify substrings.

✓ Correctly returned only single-character partitions for no longer palindrome substrings.

t3_01corner

Input{"s":"abaaba"}

Expected[["a","b","a","a","b","a"],["a","b","a","aba"],["a","b","aa","b","a"],["a","baab","a"],["aba","a","b","a"],["aba","aba"],["abaaba"]]

⏱ Performance - must finish in 2000ms

Complex palindrome partitions including nested palindromes like 'aba', 'aa', 'baab'.

💡 Greedy approach picking largest palindrome first may miss some partitions.

💡 Backtracking must explore all splits, not just longest palindromes.

💡 Check all substring lengths at each step to find all palindrome partitions.

Why it failed: Greedy approach missed some partitions by always choosing longest palindrome first. Fix by exploring all substring splits.

✓ All palindrome partitions including nested palindromes correctly found.

t3_02corner

Input{"s":"abba"}

Expected[["a","b","b","a"],["a","bb","a"],["abba"]]

⏱ Performance - must finish in 2000ms

Tests correct handling of even-length palindrome 'bb' and full palindrome 'abba'.

💡 Check palindrome detection for even length substrings.

💡 Backtracking must consider substrings of all lengths including even lengths.

💡 Ensure palindrome check handles even length substrings correctly.

Why it failed: Failed to detect even length palindrome substrings like 'bb' or 'abba'. Fix palindrome check to handle even length substrings.

✓ Correctly detected even length palindrome substrings and generated all partitions.

t3_03corner

Input{"s":"abcba"}

Expected[["a","b","c","b","a"],["a","bcb","a"],["abcba"]]

⏱ Performance - must finish in 2000ms

Tests palindrome partitions including odd length palindrome 'bcb' and full palindrome 'abcba'.

💡 Check palindrome detection for odd length substrings.

💡 Backtracking must explore all substring lengths.

💡 Ensure palindrome check correctly identifies palindromes in middle of string.

Why it failed: Missed odd length palindromes like 'bcb' or full palindrome 'abcba'. Fix palindrome check and backtracking to include all valid substrings.

✓ Correctly found all palindrome partitions including odd length palindromes.

t4_01performance

Input{"s":"aaaaaaaaaaaaaaaa"}

Expectednull

⏱ Performance - must finish in 2000ms

Input string of length 16 with all identical characters. Algorithm must run in O(N*2^N) time within 2 seconds.

💡 Backtracking with memoization or dynamic palindrome checks can optimize performance.

💡 Avoid repeated palindrome checks by caching results.

💡 Use pruning to reduce unnecessary recursive calls.

Why it failed: Algorithm timed out due to exponential complexity without memoization or pruning. Optimize palindrome checks and use memoization to pass.

✓ Algorithm completed within time limit using efficient palindrome checks and pruning.

Practice

1. Examine the following buggy code snippet for Expression Add Operators. Which line contains the subtle bug that causes incorrect results on inputs with leading zeros?

def addOperators(num: str, target: int) -> List[str]:
    res = []
    path = []
    def backtrack(index: int, evaluated: int, last_operand: int):
        if index == len(num):
            if evaluated == target:
                res.append(''.join(path))
            return
        for i in range(index, len(num)):
            # Bug: missing leading zero check
            curr_str = num[index:i+1]
            curr = int(curr_str)
            length_before = len(path)
            if index == 0:
                path.append(curr_str)
                backtrack(i+1, curr, curr)
                path[length_before:] = []
            else:
                path.append('+'); path.append(curr_str)
                backtrack(i+1, evaluated + curr, curr)
                path[length_before:] = []
    backtrack(0, 0, 0)
    return res

medium

A. Line with 'if i != index and num[index] == '0':' missing here

B. Line with 'curr_str = num[index:i+1]' (substring extraction)

C. Line with 'path[length_before:] = []' (backtracking cleanup)

D. Line with 'path.append('+'); path.append(curr_str)' (operator insertion)

Solution

1. Step 1: Identify handling of leading zeros

   The code lacks the check 'if i != index and num[index] == '0': break' which prevents invalid operands like "05".

2. Step 2: Confirm bug location

   This missing check is critical and should be placed before parsing curr_str to avoid invalid expressions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing leading zero check causes invalid operands [OK]

Hint: Leading zero check missing causes invalid operands [OK]

Common Mistakes:

• Confusing backtracking cleanup lines as bug
• Thinking substring extraction is buggy

2. Consider the following buggy code for generating letter combinations. Which line contains the subtle bug that causes incorrect or incomplete results?

from collections import deque

def letterCombinations(digits):
    if digits == '':
        return ['']
    digit_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
                 '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    queue = deque([''])
    for digit in digits:
        letters = digit_map[digit]
        for _ in range(len(queue)):
            prev = queue.popleft()
            for char in letters:
                queue.append(prev + char)
    return list(queue)

medium

A. Line 7: letters = digit_map[digit]

B. Line 2: if digits == '': return ['']

C. Line 10: prev = queue.popleft()

D. Line 1: from collections import deque

Solution

1. Step 1: Analyze empty input handling

   Returning [''] for empty input is incorrect; the problem expects an empty list [] when input is empty.

2. Step 2: Check other lines

   Digit mapping, queue operations, and imports are correct and do not cause bugs.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Empty input should return [] not [''] to match problem spec [OK]

Hint: Empty input must return empty list, not list with empty string [OK]

Common Mistakes:

• Returning [''] instead of [] for empty input
• Assuming digits '1' or '0' map to letters

3. The following code attempts to generate all permutations of a list using Heap's algorithm but contains a subtle bug:

def permute(nums):
    res = [nums[:]]
    c = [0] * len(nums)
    i = 0
    while i < len(nums):
        if c[i] < i:
            if i % 2 == 0:
                nums[0], nums[i] = nums[i], nums[0]
            else:
                nums[c[i]], nums[i] = nums[i], nums[c[i]]
            res.append(nums)
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return res

What is the bug in this code?

medium

A. The used array c is not reset properly, causing infinite loop

B. Appending nums directly without copying causes all entries in res to reference the same list

C. Swapping nums[0] and nums[i] when i is even is incorrect logic

D. The initial res list should be empty, not contain nums[:] at start

Solution

1. Step 1: Identify how results are stored

   The code appends nums directly to res without copying.

2. Step 2: Understand consequences of appending references

   Since nums is mutated in-place, all entries in res point to the same list, resulting in duplicates of the final permutation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending a copy nums[:] fixes the bug [OK]

Hint: Always append a copy of mutable lists to results [OK]

Common Mistakes:

• Forgetting to copy before appending results in duplicate references

4. What is the time complexity of the optimal iterative backtracking solution with pruning for restoring IP addresses from a string of length n, and why?

medium

A. O(3^4) because each of the 4 segments can be length 1 to 3, and pruning limits exploration

B. O(4^n) because each character can start a new segment or continue the previous one

C. O(n^4) because we try all partitions of the string into 4 segments

D. O(n!) due to permutations of segment lengths

Solution

1. Step 1: Identify branching factor per segment

   Each segment can be length 1, 2, or 3, so branching factor is at most 3 per segment.

2. Step 2: Calculate total combinations

   There are 4 segments, so total combinations are at most 3^4 = 81. Pruning further reduces this.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time complexity depends on fixed 4 segments with max 3 choices each [OK]

Hint: Fixed 4 segments with max 3 lengths each -> 3^4 complexity [OK]

Common Mistakes:

• Assuming complexity depends on n^4
• Confusing permutations with combinations

5. Suppose you want to generate all permutations of an array where elements can be repeated any number of times (i.e., unlimited reuse of elements). Which modification to the standard backtracking approach is correct?

hard

A. Remove the used array entirely and allow elements to be chosen multiple times at each recursion level

B. Use the same backtracking with a used array but reset used[i] to false only after the entire recursion finishes

C. Use in-place swapping but skip swapping elements that have been used before in the current recursion path

D. Generate permutations normally and then filter out duplicates after generation

Solution

1. Step 1: Understand the problem variant

   Elements can be reused unlimited times, so no need to track usage.

2. Step 2: Modify backtracking accordingly

   Removing the used array allows choosing any element at each recursion level multiple times, generating permutations with repetition.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Allowing repeated choices without usage tracking fits unlimited reuse [OK]

Hint: Unlimited reuse means no used array needed [OK]

Common Mistakes:

• Keeping used array causes missing permutations or incorrect pruning