Palindrome Partitioning
- 3 days ago
- 8 min read
Disciplined Recursion Over a String
Palindrome Partitioning is a backtracking problem that tests whether you can explore a decision tree methodically while pruning invalid paths early. If you've worked through Combination Sum or Word Break, you'll recognize pieces of both here: the recursive partitioning structure from one, and the prefix-based thinking from the other.
Problem Statement
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings.
A palindrome reads the same forward and backward. Single characters always qualify.
Examples:
"aab" → [["a","a","b"], ["aa","b"]]
"aaa" → [["a","a","a"], ["a","aa"], ["aa","a"], ["aaa"]]
"abc" → [["a","b","c"]]
1. Clarify Requirements Before Jumping Into Code
Before writing anything, restate the rules clearly.
Input: A non-empty string s.
Output: A list of lists of strings, where each inner list is a valid partition. A valid partition is one where every substring in it is a palindrome.
Key clarifications:
Every character must be used. This isn't about selecting subsets - it's about covering the entire string with palindromic cuts.
All possible partitions must be returned, not just one.
Single characters are always palindromes, so a partition into individual characters always qualifies.
This is enumeration, not optimization - we're not finding the fewest cuts or the longest palindromes.
2. Identify the Category of the Problem
The structure is close to what we saw in Combination Sum: at each step, we choose how far to extend the current segment, validate the choice, and recurse on what's left. What's new is the validation condition - instead of checking a running sum, we check whether the current substring is a palindrome.
This is sounding like we will need to apply backtracking over a string - specifically, recursive partitioning where we validate each segment before committing to it.
3. Start With Brute Force to Build Intuition
The brute force approach is to generate every possible way to split the string into substrings, then filter the partitions where every substring is a palindrome.
For a string of length n, there are n-1 possible cut positions, each either taken or not - that's 2^(n-1) possible partitions. For n = 15, that's 16,384. For each partition, checking all substrings takes O(n²) time. And most partitions get rejected late, after we've already checked several valid prefixes only to find an invalid suffix.
The waste is in the late rejection. A partition like ["not-palindrome", ...] should be rejected the moment we commit to the first segment, not after exploring everything downstream.
4. Brainstorm More Solutions
Step 1: Think in Terms of Positions, Not Substrings
The brute force failed because it separated two things that could happen together: splitting and validating. It generated a complete partition first, then checked whether it was valid, meaning it could do enormous amounts of work on a partition, only to reject it at the last segment.
So let's ask ourselves: when exactly do we know a partition is going to fail? We know the moment we commit to a segment that isn't a palindrome. We don't need to see the rest of the partition to know it's invalid.
That observation suggests a different question to ask at each step. Instead of "is this entire partition valid?", ask something smaller and more immediate: "what's the shortest valid first cut I can make right now?"
More precisely: given that we've already placed some segments and we're currently at position start, what are our options for the next segment? We try ending it at start, then start+1, then start+2, and so on - checking each candidate against the palindrome condition. If a candidate passes, we commit to it and ask the same question starting from the next position. If it fails, we simply don't recurse - we try a longer ending instead.
Notice what this buys us: an invalid segment never spawns a recursive call. We don't explore any downstream partitions that would have started with a non-palindrome. The invalid path is cut off at the exact moment we could have detected it.
Step 2: Define the Recursive State
What does each call need to know?
start: Where in the string we're currently trying to cut from.
path: The segments chosen so far.
Base case: when start == s.length(), we've covered the entire string with palindromic segments. Record the current path and return.
Recursive case: for each end from start to n-1, check if s[start...end] is a palindrome. If yes, add the segment, recurse with start = end + 1, then remove the segment (backtrack).
Step 3: Trace Through an Example
Let's trace "aab":
backtrack(start=0, path=[])
end=0: s[0:0]="a" → palindrome ✓
backtrack(start=1, path=["a"])
end=1: s[1:1]="a" → palindrome ✓
backtrack(start=2, path=["a","a"])
end=2: s[2:2]="b" → palindrome ✓
backtrack(start=3, path=["a","a","b"])
start==length → record ["a","a","b"] ✓
end=2: s[1:2]="ab" → not palindrome, skip
remove "a"
end=1: s[0:1]="aa" → palindrome ✓
backtrack(start=2, path=["aa"])
end=2: s[2:2]="b" → palindrome ✓
backtrack(start=3, path=["aa","b"])
start==length → record ["aa","b"] ✓
remove "aa"
end=2: s[0:2]="aab" → not palindrome, skipResult: [["a","a","b"], ["aa","b"]]. Notice that "aab" was checked and skipped without spawning any recursive call - exactly the pruning we wanted.
Step 4: How Expensive Is the Palindrome Check?
Each call to isPalindrome(start, end) takes O(end - start) time - proportional to the length of the substring being checked. In the worst case (a string of all identical characters like "aaaa"), every substring is a palindrome and we check many of them repeatedly. For "aaa", substring s[0:1] gets checked multiple times from different recursive paths.
This redundancy points to an optimization: we can store the results of our palindrome checks in a 2D boolean table dp[i][j] where dp[i][j] = true if s[i...j] is a palindrome. We can build it once in O(n²) time and space, then each check during backtracking is O(1).
The recurrence for the DP table: s[i...j] is a palindrome if s[i] == s[j] and either the substring is length 1 or 2 (base cases) or s[i+1...j-1] is also a palindrome.
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j)
&& (j - i <= 2 || dp[i + 1][j - 1]);
}
}With this table, isPalindrome(i, j) becomes dp[i][j] - a single array lookup.
Is this optimization necessary? For most interview inputs (strings of length ≤ 16), the repeated O(n) checks are fast enough. The DP table is worth mentioning and worth implementing, especially if the interviewer asks about optimization, but it's not required for a correct solution.
Step 5: Connect to Word Break
It's worth pausing to notice the structural similarity to Word Break. In that problem, we asked: "which positions in the string are reachable, where reachable means the prefix ending here can be segmented into dictionary words?" Here we're asking: "which ways can the entire string be cut into palindromic segments?"
Both problems think in terms of prefix endpoints. Both validate a segment (dictionary membership vs. palindrome check) before committing. The difference is that Word Break asked a boolean question (can it be done?) while this problem asks for enumeration (give all ways). That's why Word Break used bottom-up DP - it only needed to know reachability, not reconstruct paths. Here, we need the paths themselves, so backtracking is the right tool.
5. Trade-Offs at a Glance
Approach | Time | Space | Notes |
Generate all splits, then filter | O(n · 2^n) | Large | Late rejection; wasteful |
Backtracking + inline palindrome check | O(n · 2^n) | O(n) | Standard solution; some repeated work |
Backtracking + DP palindrome table | O(n · 2^n) | O(n²) | O(1) palindrome checks; worth mentioning |
The time complexity warrants careful thought. There are at most 2^(n-1) partitions (each of the n-1 gaps is either a cut or not). For each partition found, we copy a path of up to n segments - O(n) work. So the output-sensitive bound is O(n · 2^n). The palindrome checks add work proportional to the total characters examined, which is also bounded by O(n · 2^n) in the worst case. Pruning reduces the constant factor dramatically for strings that aren't all-identical characters.
6. Pseudocode
result = empty list
backtrack(start, path):
if start == s.length:
add copy of path to result
return
for end from start to s.length - 1:
if isPalindrome(s, start, end):
add s[start:end+1] to path
backtrack(end + 1, path)
remove last element from path
call backtrack(0, empty path)7. Edge Cases
Single character: One partition containing that character. The loop runs once, isPalindrome returns true trivially, the base case fires immediately on recursion.
All identical characters: Every substring is a palindrome - maximum branching, maximum output. For "aaa", all four partitions are valid. Good stress test.
No multi-character palindromes: Like "abc". Only one partition - all single characters. The loop tries multi-character prefixes, finds none are palindromes, and only recurses on single characters.
Entire string is a palindrome: Like "aba". Both ["a","b","a"] and ["aba"] are valid. The loop correctly finds both.
8. Full Solution
import java.util.ArrayList;
import java.util.List;
public class PalindromePartitioning {
public static List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), result);
return result;
}
private static void backtrack(String s, int start,
List<String> path,
List<List<String>> result) {
if (start == s.length()) {
// copy — not a reference
result.add(new ArrayList<>(path));
return;
}
for (int end = start; end < s.length(); end++) {
if (isPalindrome(s, start, end)) {
path.add(s.substring(start, end + 1)); // choose
backtrack(s, end + 1, path, result); // explore
path.remove(path.size() - 1); // un-choose
}
// if not a palindrome, don't recurse — natural pruning
}
}
private static boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left++) != s.charAt(right--))
return false;
}
return true;
}
}Notice that the pruning isn't explicit - there's no continue or break. We simply don't add the segment or recurse when isPalindrome returns false. The if condition is the entire pruning mechanism.
9. Test Your Solution
System.out.println(partition("a"));
// [[a]]
System.out.println(partition("aab"));
// [[a, a, b], [aa, b]]
System.out.println(partition("aba"));
// [[a, b, a], [aba]]
System.out.println(partition("aaa"));
// [[a, a, a], [a, aa], [aa, a], [aaa]]
System.out.println(partition("abc"));
// [[a, b, c]]10. Key Lessons for Future Problems
Validate before recursing, not after. The pruning in this problem is a single if condition. By only recursing when the current segment is a valid palindrome, we eliminate entire subtrees of invalid paths without ever entering them. This is the same principle as checking remaining < 0 before recursing in Combination Sum - reject bad choices at the point of commitment, not downstream.
Partitioning problems are naturally recursive. Any problem that asks you to split a sequence into valid segments has this structure: pick a prefix, validate it, recurse on the suffix. The validation condition changes (palindrome here, dictionary word in Word Break, valid expression elsewhere), but the skeleton is the same.
Know when DP preprocessing pays off. The repeated palindrome checks are the one inefficiency in the basic solution. If an interviewer pushes on optimization, the 2D DP table is the right answer - precompute all palindrome substrings once, then look them up in O(1) during backtracking. Mentioning this proactively, even without implementing it, signals that you're thinking about the full solution space.
Recognize the connection to Word Break. Both problems partition a string by validating segments. Word Break asks whether a partition exists (boolean DP). This problem asks for all valid partitions (backtracking). Understanding why one calls for DP and the other for backtracking is a sign of deep pattern recognition.
Palindrome Partitioning rewards disciplined recursion. Control the cuts, validate early, clean up state faithfully, and the algorithm handles the rest.
Good Luck and Happy Coding!
Comments