Compile Ready
Module 5 · String Backtracking

Palindrome Partitioning

MediumProblem 10 of 17 9 min read ~22 min to solve LeetCode
BacktrackingStringPartitioningPalindromeDFSPruning
Asked atAmazonGoogleMicrosoftMetaAdobe

Problem Statement

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

Input

A lowercase string s that must be split into contiguous substrings.

Output

A list of partitions, where each partition is a list of palindromic substrings whose concatenation equals s.

Constraints

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

Examples

Example 1

Input: 
s = aab
Output: [[a,a,b],[aa,b]]
Explanation: Both **a | a | b** and **aa | b** use only palindrome pieces. The cut **a | ab** is rejected because **ab** is not a palindrome.

Example 2

Input: 
s = a
Output: [[a]]
Explanation: The whole one-character string is a palindrome, so there is exactly one partition.

Example 3

Input: 
s = efe
Output: [[e,f,e],[efe]]
Explanation: Single characters are always palindromes, and the entire string **efe** is also a palindrome.

Learning Objectives

  • Recognise palindrome partitioning as a **choose a prefix cut, recurse on the suffix** problem.
  • Use the current **start** index and current list of pieces as the recursion state.
  • Prune immediately when a candidate prefix is not a palindrome.
  • Compare on-demand palindrome checks with a precomputed palindrome table.

Intuition

Pattern Recognition

This is the cut and partition string pattern. At any start index, the next decision is where to cut the next prefix: s[start...end]. If that prefix is a palindrome, it can be appended to the current partition and the rest of the problem is exactly the suffix starting at end + 1.

The key is to avoid thinking about all dot placements first. Backtracking naturally builds one valid piece at a time. Invalid prefixes are pruned before recursion, so every recursive call represents a path whose pieces are all palindromes so far. When start == s.length, every character has been consumed and the current path is one complete partition.

Common mistakes

  • ×Recursing on non-palindrome prefixes and filtering only at the end, which creates unnecessary branches.
  • ×Recording the mutable path directly instead of adding a copy to the result.
  • ×Using **substring(start, end)** as if the end index were inclusive in Java.
  • ×Stopping after finding the first valid partition even though the problem asks for all partitions.

Algorithm Explanation

State

Each frame carries start, the first unpartitioned index, and path, the palindrome pieces selected so far. A candidate choice is an inclusive cut end from start to the final index. Choosing the prefix s[start...end] moves the next frame to end + 1.

Recursion tree

For s = aab, the root starts at index 0. The cut a is a palindrome, so the path becomes [a] and recursion starts at index 1. From there, cut a is valid, then cut b is valid, recording [a,a,b]. Still under [a], the cut ab is not a palindrome and is pruned. Back at the root, cut aa is valid, then b completes [aa,b]. The root cut aab is not a palindrome and is pruned.

Pruning

The main pruning rule is the palindrome test: if s[start...end] is not a palindrome, skip that cut and do not recurse. A precomputed palindrome table can make this check O(1), but the search tree is the same. Single-character prefixes always pass, which guarantees progress.

Algorithm

  1. Create an empty result list and an empty path.
  2. Start DFS with start = 0.
  3. If start == s.length, copy path into the result.
  4. For every end from start through the last index, test whether s[start...end] is a palindrome.
  5. If it is not a palindrome, continue to the next cut.
  6. Choose the prefix by appending it to path, then recurse from end + 1.
  7. Unchoose by removing the last piece before trying the next cut.

Solutions

Solution 1: Backtracking with on-demand palindrome checks

Try every possible next cut, but recurse only when the chosen prefix is a palindrome. This is the cleanest interview implementation because the palindrome check is local and the recursion mirrors the definition of a valid partition.

Step-by-step

  1. Start from index 0 with an empty path.
  2. In each frame, scan all end positions for the next prefix.
  3. Use a two-pointer check to reject non-palindrome prefixes immediately.
  4. Append each valid prefix, recurse on the suffix after it, and remove the prefix afterward.
  5. When the start index reaches the string length, copy the current path into the result.
Time

O(n^2 * 2^n)

Space

O(n)

There are exponentially many cut patterns, and each on-demand palindrome check can scan O(n) characters. Auxiliary recursion and path space are O(n), excluding output.

Java implementation

Loading…

Solution 2: Backtracking with precomputed palindrome table

When the interviewer cares about repeated palindrome checks, precompute whether every substring is a palindrome. The DFS is unchanged, but each candidate prefix can be accepted or rejected in O(1).

Step-by-step

  1. Build a boolean table where palindrome[start][end] says whether s[start...end] is a palindrome.
  2. Fill the table by increasing substring length so inner substrings are known first.
  3. Run the same start-index DFS as the on-demand version.
  4. For each cut, consult the table instead of scanning with two pointers.
  5. Copy the path when the start index reaches the end of the string.
Time

O(n^2 + n * 2^n)

Space

O(n^2)

The table costs O(n^2). DFS still has exponentially many outputs, and copying a completed partition can cost O(n).

Java implementation

Loading…

Dry Run

Sample input

s = aab. Track each candidate cut from the current start index and whether it becomes part of the current partition.

depthstartchoicepathaction
00a[a]palindrome prefix, recurse from 1
11a[a,a]palindrome prefix, recurse from 2
22b[a,a,b]start reaches 3 after this, record partition
11ab[a]not a palindrome, prune
00aa[aa]palindrome prefix, recurse from 2
12b[aa,b]start reaches 3 after this, record partition
00aab[]not a palindrome, prune

Only two root-to-leaf paths survive the palindrome pruning: [a,a,b] and [aa,b].

Interview Tips

Explain the problem as choosing the next cut, not as rearranging characters. Then the invariant is simple: every piece already in path is a palindrome. Start with the on-demand palindrome check unless the interviewer asks about repeated work; then offer the O(1) lookup table as a clean optimization.

Likely follow-ups

  • How would you return only the minimum number of cuts needed to partition the string into palindromes?
  • How would you count the partitions without storing every partition?
  • How would the solution change if palindrome checks were case-insensitive?
  • How would you stream partitions lazily for a very large output?

Similar Problems

Restore IP Addresses
MediumAlso chooses the next string segment and recurses on the remaining suffix.
Letter Combinations of a Phone Number
MediumAnother string DFS where each level commits one piece of the output.
Combination Sum
MediumShares the choose, recurse, unchoose structure with pruning.
Palindrome Partitioning II
HardTurns the same palindrome cuts into a minimum-cut dynamic programming problem.

Key Takeaways

  • String partitioning backtracking chooses a prefix and recurses on the suffix.
  • The palindrome check is the pruning gate that prevents invalid branches from entering DFS.
  • Copy the path only when the start index has consumed the entire string.
  • Precomputing palindrome truth trades O(n^2) memory for faster repeated cut checks.
Reusable template: Cut-point DFS: from a start index, try every valid prefix, append it to the path, recurse on the suffix, and remove it before the next cut.