Palindrome Partitioning

Palindrome Partitioning

What is this problem about?

The Palindrome Partitioning problem asks you to find all possible ways to partition a string such that every substring in each partition is a palindrome. Return all valid partitions as a list of lists. This Palindrome Partitioning coding problem combines backtracking with palindrome checking, and can be optimized using DP precomputation.

Why is this asked in interviews?

Apple, Uber, Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it tests backtracking design with palindrome verification. It's a comprehensive problem that shows a candidate's ability to generate all valid configurations while pruning invalid branches early. The backtracking, string, and dynamic programming interview pattern is fully exercised.

Algorithmic pattern used

Backtracking with DP palindrome precomputation. Precompute isPalin[i][j] = whether s[i..j] is a palindrome using DP. Then backtrack: at each start index, try all end indices. If isPalin[start][end], add the substring to the current partition and recurse from end+1. When start reaches the string end, add the current partition to results.

Example explanation

s="aab". isPalin: "a"✓,"a"✓,"b"✓,"aa"✓,"ab"✗,"aab"✗. Backtrack: start=0. Try end=0: "a"✓ → recurse from 1. Try end=1: "aa"✓ → recurse from 2. Try end=2: "aab"✗ skip. From start=1: end=1 "a"✓ → recurse from 2. start=2: "b"✓ → add ["a","a","b"]. From start=1,end=2: "ab"✗. From start=2 (via aa): "b"✓ → add ["aa","b"]. Result: [["a","a","b"],["aa","b"]].

Common mistakes candidates make

• Checking palindrome naively (O(n) per check → O(n³) total) instead of precomputing.
• Not properly restoring the current path on backtrack.
• Off-by-one in the DP palindrome table.
• Not memoizing the backtrack results.

Interview preparation tip

Palindrome Partitioning is the canonical backtracking + DP combination. Always precompute the palindrome table first — it reduces each substring check from O(n) to O(1). Practice this two-phase approach: first build the DP table, then apply backtracking using O(1) palindrome checks. Palindrome Partitioning I, II, and IV form a progression where you move from all solutions to optimization.