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. Consider the following code snippet implementing the optimal backtracking solution for Word Search. Given the board = [["A","B","C"],["D","E","F"],["G","H","I"]] and word = "BEF", what is the return value of exist(board, word)?

easy

A. True

B. False

C. Raises IndexError

D. Infinite recursion

Solution

1. Step 1: Trace dfs starting at cell (0,1) 'B'

   Word starts with 'B', found at (0,1). dfs(0,1,0) matches 'B'.

2. Step 2: Explore neighbors for next chars 'E' and 'F'

   From (0,1), neighbors checked: (1,1) 'E' matches next char, then (1,2) 'F' matches last char. All matched, return True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All characters found sequentially with valid moves [OK]

Hint: Trace dfs calls carefully to confirm path exists [OK]

Common Mistakes:

• Assuming no path due to adjacency confusion
• Missing in-place marking effect

2. What is the time complexity of the optimal backtracking solution that generates all valid parentheses sequences for input n?

medium

A. O(2^{2n} * n) because it generates all sequences and checks validity

B. O(n^2) because it builds sequences of length 2n with nested loops

C. O(n!) because it permutes parentheses positions

D. O(\frac{4^n}{n^{3/2}}) because the number of valid sequences is the nth Catalan number

Solution

1. Step 1: Identify number of valid sequences

   The number of valid parentheses sequences is the nth Catalan number, approximately 4^n / (n^{3/2}).

2. Step 2: Analyze backtracking time

   Backtracking generates all valid sequences, so time is proportional to number of sequences times sequence length, which is O(4^n / n^{3/2} * n) = O(4^n / n^{1/2}).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches known Catalan number growth for valid parentheses [OK]

Hint: Catalan number growth dominates complexity [OK]

Common Mistakes:

• Confusing brute force with backtracking complexity
• Assuming factorial complexity

3. Consider this modified code snippet for generating parentheses. Which line contains a subtle bug that can cause invalid sequences to be generated?

medium

A. Line with 'if close_count <= open_count:' condition

B. Line with 's.pop()' after backtrack calls

C. Line with 'if open_count < n:' condition

D. Line with 'if len(s) == 2 * n:' base case

Solution

1. Step 1: Examine close_count condition

   The condition 'close_count <= open_count' allows adding ')' even when close_count equals open_count, which can produce invalid sequences.

2. Step 2: Correct condition

   The correct condition is 'close_count < open_count' to ensure ')' is added only when there are unmatched '('.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to '<' fixes invalid sequence generation [OK]

Hint: Close count must be strictly less than open count [OK]

Common Mistakes:

• Using <= instead of < for close_count condition
• Forgetting to pop after recursion

4. What is the time complexity of the optimal iterative approach using a queue to generate all letter combinations for a digit string of length n, assuming each digit maps to at most 4 letters?

medium

A. O(n * 4^n) because we process each digit and expand combinations exponentially

B. O(2^n) because each digit doubles the number of combinations

C. O(4^n * n) because there are up to 4^n combinations and each combination is built with n concatenations

D. O(n^2) because we process n digits and each combination takes n steps

Solution

1. Step 1: Identify number of combinations

   Each digit maps to up to 4 letters, so total combinations are up to 4^n.

2. Step 2: Analyze work per combination

   Each combination is built by concatenating letters for n digits, so each combination requires O(n) time to build.

3. Step 3: Simplify complexity expression

   O(4^n * n) and O(n * 4^n) are equivalent; however, O(n * 4^n) because we process each digit and expand combinations exponentially is the standard notation emphasizing processing each digit and expanding combinations exponentially.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Time is exponential in n with linear cost per combination [OK]

Hint: Exponential combinations times linear build cost [OK]

Common Mistakes:

• Confusing exponential base (2 vs 4)
• Ignoring concatenation cost per combination

5. What is the time complexity of the optimal backtracking algorithm that generates unique permutations of an array with duplicates by sorting and skipping duplicates during recursion?

medium

A. O(n! * log n) due to sorting and binary search for duplicates

B. O(n! * n^2) because each permutation requires copying the array and checking duplicates

C. O(n^n) because the recursion explores all possible swaps without pruning

D. O(n! * n) because pruning duplicates early reduces redundant branches but each permutation still requires O(n) copying

Solution

1. Step 1: Identify complexity of outer and inner loops

   Backtracking explores permutations, which is O(n!). Each permutation requires copying O(n) elements to result.

2. Step 2: Check if pruning duplicates reduces complexity

   Pruning duplicates early avoids redundant branches, so complexity is O(n! * n), not worse. Sorting is O(n log n) but done once.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Pruning reduces branches but copying each permutation costs O(n) [OK]

Hint: Pruning duplicates reduces branches but copying costs O(n) per permutation [OK]

Common Mistakes:

• Confusing pruning effect or ignoring copy cost