Palindrome Partitioning
Mahabharata — Vyasa's Sacred Cuts — Partition the Verse into Palindromic Segments
छंद को खंडों में बांटो — प्रत्येक खंड स्वयंविलोम। प्रत्येक संभव कट — जांचो, आगे बढ़ो॥
*Partition the verse into segments — each segment a palindrome. Try every possible cut — check, then advance.*
The Story
Partition string s such that every substring is a palindrome. Return all possible partitions.
For `s="aab"`: [["a","a","b"],["aa","b"]].
**Backtracking:** - Try all prefixes s[start..i] (for i from start to n-1) - If s[start..i] is a palindrome: add to path, recurse on s[i+1..n] - Backtrack: remove from path
```java void backtrack(List<List<String>> res, List<String> path, String s, int start) { if (start == s.length()) { res.add(new ArrayList<>(path)); return; } for (int i=start; i<s.length(); i++) { if (isPalindrome(s, start, i)) { path.add(s.substring(start, i+1)); // Choose backtrack(res, path, s, i+1); // Explore path.remove(path.size()-1); // Unchoose } } } ```
Trace `"aab"`: - start=0: try "a"(0,0)✓, "aa"(0,1)✓, "aab"(0,2)✗ - path=["a"]: start=1 - try "a"(1,1)✓, "ab"(1,2)✗ - path=["a","a"]: start=2 - try "b"(2,2)✓ - path=["a","a","b"]: start=3==len → ADD ✓ - path=["aa"]: start=2 - try "b"(2,2)✓ - path=["aa","b"]: start=3==len → ADD ✓
Result: [["a","a","b"],["aa","b"]] ✓
The Same Backtracking (Already Optimal)
Backtracking IS the standard solution. With DP precomputation of isPalindrome: O(n×2^n).
// Already optimal. For faster isPalindrome check, precompute DP table:
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]);The Try-Each-Prefix Palindrome Backtracking
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
backtrack(res, new ArrayList<>(), s, 0);
return res;
}
void backtrack(List<List<String>> res, List<String> path, String s, int start) {
if (start == s.length()) { res.add(new ArrayList<>(path)); return; }
for (int i = start; i < s.length(); i++) {
if (isPalindrome(s, start, i)) {
path.add(s.substring(start, i + 1));
backtrack(res, path, s, i + 1);
path.remove(path.size() - 1);
}
}
}
boolean isPalindrome(String s, int l, int r) {
while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
return true;
}Step-by-Step Walkthrough
s="a" start=0: i=0: "a" is palindrome → path=["a"] → start=1==1 → ADD Result: [["a"]] ✅
Deep Insight
**Optimization with DP precomputation:** isPalindrome(s, l, r) takes O(r-l) time. Called O(n²) times in backtracking → O(n³) total. Precompute dp[i][j] = is s[i..j] a palindrome in O(n²). Then each check is O(1). Total: O(n × 2^n).
**Why O(2^n)?** Each character can be a cut point or not. With n characters, 2^(n-1) possible partitions (for each of the n-1 positions between characters, either cut or no cut). Each palindrome partition is a subset of all-cut positions where all resulting segments are palindromes.
**Pattern:** Try all prefixes, filter by condition (palindrome check), recurse on suffix. This 'try all cuts' pattern appears in matrix chain multiplication, burst balloons, etc.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n³ × 2^n) | O(n) | 2^n partitions × O(n) isPalindrome check |
| Optimal | O(n × 2^n) | O(n²) | With DP precomputation of isPalindrome: O(n²) space + O(1) check |
Pattern Recognition
✅ Partition into palindromes → try-all-cuts backtracking ✅ for i from start..n-1: if palindrome(start,i) → add, recurse(i+1), remove ✅ Base: start==n → add partition ✅ Optimize: DP precompute isPalindrome in O(n²) **LeetCode Trigger Phrases:** → "palindrome partitioning" → Partition string where each part satisfies condition → Try-all-cuts backtracking pattern
Bhagavad Gita 15.1
छन्दांसि यस्य पर्णानि यः तं वेद स वेदवित्।
The Vedic hymns are the leaves of this tree; one who knows this tree knows the Vedas.
Connection: The palindrome partitioning cuts the string at every possible point where symmetry exists — like the natural division points in sacred verse. Each valid partition is a complete reading where every segment reflects back on itself. The backtracking algorithm explores all possible cuts, accepting only those where each segment is a perfect palindrome — a self-reflecting truth — just as the Vedic hymns contain complete, self-contained sacred knowledge in each verse.