Definition
- Palindrome partitioning – enumerates every way to cut a string into pieces where each piece reads the same forwards and backwards.
- Backtracking with pruning – from the current start index, try every end position; only recurse when the prefix is a palindrome.
- Completion condition – a partition is complete when the start index equals the string length.
- Palindrome check – either a two-pointer O(n) check or a precomputed O(1) lookup from a DP table.
- Exponential output – the number of valid partitions can be exponential, so the algorithm is necessarily exponential.
At the National Bank of India, a reference token must be split into symmetric segments for a legacy validator. Rajesh tries cutting after the first character, after the second, and so on. Whenever a piece is symmetric, he accepts it and recursively splits what remains. Every complete split where all pieces are symmetric is recorded.
Understanding the Concepts
What is the Palindrome Partitioning problem?
Given a string, partition it into substrings such that every substring is a palindrome, and return all possible such partitionings. For example, "AAB" can be partitioned as [["A","A","B"], ["AA","B"]].
package com.bank.core;
// Input: "AAB"
// Partition 1: ["A", "A", "B"] - each is a palindrome
// Partition 2: ["AA", "B"] - both are palindromes
// "AAB" is NOT a palindrome, so it cannot be a single-piece partition
How does the backtracking work?
You recurse with a start index and a current list of pieces. If the start index equals the string length, the current list is a complete valid partition and you record a copy. Otherwise, you loop the end index from start to the last character. For each end, you form the substring from start to end inclusive. If that substring is a palindrome, you add it to the current list, recurse with the next start being end plus one, and then remove it to backtrack.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class PalindromePartitioning {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(String s, int start,
List<String> current, List<List<String>> result) {
if (start == s.length()) {
result.add(new ArrayList<>(current)); // fresh copy
return;
}
for (int end = start; end < s.length(); end++) {
if (isPalindrome(s, start, end)) {
current.add(s.substring(start, end + 1));
backtrack(s, end + 1, current, result);
current.remove(current.size() - 1); // backtrack
}
}
}
private boolean isPalindrome(String s, int lo, int hi) {
while (lo < hi) {
if (s.charAt(lo) != s.charAt(hi)) return false;
lo++;
hi--;
}
return true;
}
public static void main(String[] args) {
PalindromePartitioning solver = new PalindromePartitioning();
System.out.println(solver.partition("AAB"));
System.out.println(solver.partition("ABBA"));
}
}
[[A, A, B], [AA, B]]
[[A, B, B, A], [A, BB, A], [ABBA]]
Why is palindrome-only recursion the key optimization?
Without the palindrome check, you would recurse on every possible prefix and check at the end whether all pieces are palindromes, generating and discarding exponentially many invalid partitions. By checking each prefix before recursing, you prune entire subtrees the moment a non-palindromic prefix is detected.
package com.bank.core;
// WRONG: recurse on all prefixes, validate at the end
// Generates massive invalid trees before rejecting
// CORRECT: check palindrome before recursing
if (isPalindrome(s, start, end)) {
// Only recurse when this prefix is a palindrome
// All other prefixes are pruned immediately
}
How do you precompute palindrome checks with DP?
The two-pointer palindrome check is O(n) per call, and the same substrings may be checked repeatedly across different branches. A precomputed DP table dp[i][j] where true means the substring from i to j is a palindrome reduces each check to O(1). The table is filled for all lengths: single characters are always palindromes, pairs check equality, and longer substrings check dp[i+1][j-1] && s[i] == s[j].
package com.bank.service;
public class PalindromePartitioningOptimized {
public java.util.List<java.util.List<String>> partition(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
// Precompute palindrome table
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = (j - i <= 2) || dp[i + 1][j - 1];
}
}
}
java.util.List<java.util.List<String>> result = new java.util.ArrayList<>();
backtrack(s, 0, new java.util.ArrayList<>(), result, dp);
return result;
}
private void backtrack(String s, int start,
java.util.List<String> current,
java.util.List<java.util.List<String>> result,
boolean[][] dp) {
if (start == s.length()) {
result.add(new java.util.ArrayList<>(current));
return;
}
for (int end = start; end < s.length(); end++) {
if (dp[start][end]) {
current.add(s.substring(start, end + 1));
backtrack(s, end + 1, current, result, dp);
current.remove(current.size() - 1);
}
}
}
}
What are the edge cases?
Edge cases include: a single character (one partition of one piece), an empty string (one empty partition), a string that is itself a palindrome (includes the whole string as a single piece), and a string with all identical characters (many partitions including every possible split).
package com.bank.core;
// Edge case 1: "A" -> [["A"]] (single character)
// Edge case 2: "" -> [[]] (one empty partition)
// Edge case 3: "ABBA" -> includes ["ABBA"] as one partition
// Edge case 4: "AAA" -> [["A","A","A"],["A","AA"],["AA","A"],["AAA"]]
How is this related to Palindrome Partitioning II (minimum cuts)?
Palindrome Partitioning I (this problem) enumerates all valid partitions using backtracking. Palindrome Partitioning II asks for the minimum number of cuts to partition the string into palindromes, which is a different DP problem. The precomputed palindrome table is useful for both.
| Problem | Goal | Approach | Complexity |
|---|---|---|---|
| Partition I | All valid partitions | Backtracking | Exponential (output-sensitive) |
| Partition II | Minimum cuts | DP | O(n^2) |
package com.bank.core;
// Partition I: enumerate all -> backtracking, exponential
// Partition II: count minimum cuts -> DP, O(n^2)
// Both use a palindrome precomputation table
What about a banking use case?
At the National Bank of India, a legacy validator requires reference tokens to be split into symmetric segments. Rajesh generates all valid segmentations to test the validator thoroughly.
package com.bank.service;
import java.util.List;
public class TokenSegmentationTester {
private final PalindromePartitioning solver = new PalindromePartitioning();
public void testAllSegmentations(String token) {
List<List<String>> partitions = solver.partition(token);
System.out.println("Token: " + token);
System.out.println("Valid palindrome segmentations: " + partitions.size());
for (List<String> p : partitions) {
System.out.println(" " + p);
}
}
public static void main(String[] args) {
TokenSegmentationTester tester = new TokenSegmentationTester();
tester.testAllSegmentations("ABBA");
}
}
Token: ABBA
Valid palindrome segmentations: 3
[A, B, B, A]
[A, BB, A]
[ABBA]
What are common mistakes?
The most common mistake is forgetting to create a fresh copy of the current list when recording a complete partition. Without new ArrayList<>(current), all recorded entries share the same list object, which is empty after all backtracking completes. Another mistake is forgetting the backtrack step (removing the last element after recursion).
package com.bank.core;
// WRONG: recording a reference to the mutable list
result.add(current); // all entries share the same list!
// CORRECT: recording a fresh copy
result.add(new ArrayList<>(current));
// WRONG: forgetting to backtrack
current.add(substring);
backtrack(s, end + 1, current, result);
// Missing: current.remove(current.size() - 1);
What should a senior engineer know?
A senior engineer should know that the palindrome DP precomputation changes the per-check cost from O(n) to O(1), which matters when the string has many palindromic substrings and the recursion tree is deep. The overall complexity is still exponential because it is bounded by the output size, but the precomputation removes a linear factor from each node in the recursion tree. The choice of cut positions is a subset-style exploration, connecting this to the Subsets pattern family.
package com.bank.core;
// Senior notes:
// 1. Palindrome DP precomputation: O(n^2) setup, O(1) per check
// 2. Without DP: O(n) per check, adds linear factor to each recursion node
// 3. Output-sensitive: exponential in worst case (e.g., "AAAA...")
// 4. Subset-style exploration: each cut position is a choice
// 5. Fresh copy of current list is mandatory on recording
Visual Overview
Backtracking tree for "AAB":
backtrack(start=0, current=[])
|
|-- prefix "A" (palindrome)
| backtrack(start=1, current=["A"])
| |
| |-- prefix "A" (palindrome)
| | backtrack(start=2, current=["A","A"])
| | |
| | |-- prefix "B" (palindrome)
| | | backtrack(start=3, current=["A","A","B"])
| | | start==3 -> RECORD ["A","A","B"]
| | |
| | |-- prefix "AB" (NOT palindrome) -> PRUNE
| |
| |-- prefix "AB" (NOT palindrome) -> PRUNE
|
|-- prefix "AA" (palindrome)
| backtrack(start=2, current=["AA"])
| |
| |-- prefix "B" (palindrome)
| | backtrack(start=3, current=["AA","B"])
| | start==3 -> RECORD ["AA","B"]
|
|-- prefix "AAB" (NOT palindrome) -> PRUNE
Result: [["A","A","B"], ["AA","B"]]
Key: non-palindrome prefixes are pruned immediately,
avoiding recursion into their subtrees.
Key Takeaway
Palindrome Partitioning enumerates every way to cut a string into pieces where each piece is a palindrome. You solve it with backtracking from a start index. From the current start, you try every end position to form a prefix, and only when that prefix is a palindrome do you accept it into the current partition and recurse on the remainder. When the start index reaches the end of the string, the current list of pieces is a complete valid partition and you record a fresh copy.
The key optimization is that you recurse only on palindromic prefixes, which prunes the enormous number of invalid cuts immediately rather than building them and rejecting them later. A two-pointer palindrome check runs in O(n) per call, and the same substrings may be tested across different branches. Precomputing a palindrome DP table makes each check O(1), removing a linear factor from each node in the recursion tree.
The overall complexity is still exponential because it is bounded by the number of valid palindromic partitions, which can be exponential for strings like "AAAA...". But the palindrome-only pruning and the DP precomputation ensure that no work is wasted on invalid branches. Recording a fresh copy of the current list at each complete partition is mandatory to avoid sharing a mutable reference across all results.
At the National Bank of India, Rajesh used this to generate all valid symmetric segmentations of reference tokens for a legacy validator test suite. The backtracking produced every valid split, and the palindrome pruning kept the search efficient for tokens with few palindromic substrings. The precomputed palindrome table was reused across multiple tokens.
Remember one sentence: from each start, try every prefix, recurse only if it is a palindrome, and record the partition when the whole string is consumed.
---