How do you approach Palindrome Partitioning?

At each index, try every prefix that is a palindrome and recurse on the rest.

What are common mistakes on Palindrome Partitioning?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

gitGood.dev

← Back to problems

Palindrome Partitioning

MediumAlgorithms

Description

Given a string s, partition it so that every substring of the partition is a palindrome. Return all possible palindrome partitionings.

Partitions are listed in the order produced by exploring shorter leading cuts first.

Example 1

Input: s = "aab"

Output: [["a","a","b"],["aa","b"]]

Explanation: Two valid palindrome partitions.

Constraints

- 1 <= s.length <= 16 - s contains only lowercase English letters

Palindrome Partitioning: approach, complexity and pitfalls

A medium backtracking problem, graded against 6 test cases (4 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

If you are stuck

Show the 2-step hint ladder

At each index, try every prefix that is a palindrome and recurse on the rest.
A two-pointer check tells you whether a substring is a palindrome.

The optimal approach

Show the approach: The approach

Backtracking with palindrome check. From `start`, extend `end` and whenever `s[start..end]` is a palindrome, take it as the next piece and recurse from `end + 1`. When `start` reaches the end, record the partition.

Time: O(n·2ⁿ). Space: O(n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.