210. Palindrome Partitioning
🔗 LeetCode Problem: 131. Palindrome Partitioning
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, Backtracking, String, 1D DP
Problem Statement
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
Note: The same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Example 2:
Input: s = "a"
Output: [["a"]]
Constraints:
- 1 <= s.length <= 16
- s contains only lowercase English letters.
🌳 Visual Understanding - Using "aabb"
The Problem We're Solving:
Given: String "aabb"
Goal: Find ALL ways to partition into palindromes
Palindrome: Reads same forwards and backwards
"a" → palindrome ✓
"aa" → palindrome ✓
"aab" → NOT palindrome ✗
"b" → palindrome ✓
"bb" → palindrome ✓
"aabb" → NOT palindrome ✗
Question: How many different ways can we split "aabb"? 🤔
Finding All Valid Partitions for "aabb":
String: "aabb"
Partition 1: ["a", "a", "b", "b"]
✓ "a" is palindrome
✓ "a" is palindrome
✓ "b" is palindrome
✓ "b" is palindrome
VALID! ✓
Partition 2: ["a", "a", "bb"]
✓ "a" is palindrome
✓ "a" is palindrome
✓ "bb" is palindrome
VALID! ✓
Partition 3: ["aa", "b", "b"]
✓ "aa" is palindrome
✓ "b" is palindrome
✓ "b" is palindrome
VALID! ✓
Partition 4: ["aa", "bb"]
✓ "aa" is palindrome
✓ "bb" is palindrome
VALID! ✓
Invalid Partition: ["aab", "b"]
✗ "aab" is NOT palindrome
INVALID! ✗
Invalid Partition: ["aabb"]
✗ "aabb" is NOT palindrome
INVALID! ✗
Total: 4 valid partitions
Answer: [["a","a","b","b"], ["a","a","bb"], ["aa","b","b"], ["aa","bb"]]
Complete Decision Tree for "aabb":
"aabb"
|
+-----------------+------------------+
| | |
Take "a" Take "aa" Take "aab"
(palin ✓) (palin ✓) (palin ✗)
| | DEAD END
v v
"abb" "bb"
| |
+----+----+ +----+----+
| | | |
"a" "ab" "b" "bb"
(palin✓) (palin✗) (palin✓) (palin✓)
| DEAD | |
v v v
"bb" "b" ""
| (palin✓) [Path 4]
| | ["aa","bb"] ✓
| v
| ""
| [Path 3]
| ["aa","b","b"] ✓
|
+--+--+
| |
"b" "bb"
(✓) (✓)
| |
v v
"b" ""
(✓) [Path 2]
| ["a","a","bb"] ✓
v
""
[Path 1]
["a","a","b","b"] ✓
Total: 4 valid partitions found!
Why This Is Interesting:
Same string, MULTIPLE valid ways to partition!
"aabb" can be split as:
1. Four single chars
2. Two singles + one double
3. One double + two singles
4. Two doubles
Each partition has ALL palindromic substrings!
This is what makes the problem challenging! 🎯
🧠 The AHA Moment - Why This Problem Needs Special Approach
What Makes This Hard?
CHALLENGE 1: We need to find ALL valid partitions
- Not just count them
- Not just check if possible
- Actually GENERATE every valid partition!
CHALLENGE 2: Checking palindromes is expensive
- For "aabb", we check:
- "a" (index 0-0)
- "aa" (index 0-1)
- "aab" (index 0-2)
- "aabb" (index 0-3)
- "a" (index 1-1) ← REPEATED!
- "ab" (index 1-2)
- "abb" (index 1-3)
- ... many more!
Same substrings checked multiple times! ⚠️
CHALLENGE 3: Backtracking is necessary
- Must try every possible cut position
- Must validate each choice
- Must collect all valid paths
This needs BOTH Backtracking AND DP! 🎯
The Key Insight:
TWO-PHASE APPROACH:
PHASE 1 (DP): Precompute which substrings are palindromes
Build a table: dp[i][j] = is s[i..j] a palindrome?
Do this ONCE, use many times!
Time: O(n²)
PHASE 2 (Backtracking): Generate all valid partitions
At each position, try all palindromic cuts
Use precomputed table for O(1) palindrome check
Collect all complete valid partitions
Time: O(n × 2^n)
Why this works:
- DP eliminates repeated palindrome checks
- Backtracking systematically explores all possibilities
- Combined = optimal solution! 🚀
🔴 Approach 1: Backtracking Only (No DP Optimization)
📐 Function Definition
Function Signature:
List<List<String>> partition(String s)
void backtrack(String s, int start, List<String> current, List<List<String>> result)
boolean isPalindrome(String s, int left, int right)
What it represents:
Input Parameter s:
- The string to partition
- Example: s = "aabb"
Input Parameter start:
- Current position where we're making partition decision
- Example: start=2 means "decide how to partition from index 2"
Input Parameter current:
- Current partition being built (list of palindromic substrings found so far)
- Example: ["a", "a"] means we've partitioned first two characters
Input Parameter result:
- Collection of all complete valid partitions
Return Value: - List of all valid palindrome partitions
Purpose: - Try every possible way to cut the string - Check if each piece is a palindrome - Collect all valid complete partitions
Key Understanding:
backtrack("aabb", 0, [], result) means:
"Find all ways to partition 'aabb' starting from index 0"
At index 0 with string "aabb":
Try: cut after 1 char → "a" + recurse on "abb"
Try: cut after 2 chars → "aa" + recurse on "bb"
Try: cut after 3 chars → "aab" + recurse on "b"
Try: cut after 4 chars → "aabb" + done
For each cut that creates a palindrome, explore further
💡 Intuition
The intuition is simple: Try every possible way to make the first cut, then recursively solve the rest.
Think of it like cutting a rope:
"aabb" - where should I make the first cut?
Option 1: Cut after "a"
→ Got "a" (palindrome ✓)
→ Now solve "abb"
Option 2: Cut after "aa"
→ Got "aa" (palindrome ✓)
→ Now solve "bb"
Option 3: Cut after "aab"
→ Got "aab" (NOT palindrome ✗)
→ Don't explore this path
Option 4: Cut after "aabb"
→ Got "aabb" (NOT palindrome ✗)
→ Don't explore this path
For each valid first cut, recursively find all ways
to partition what's left!
This naturally explores ALL possible partition combinations!
The Backtracking Pattern:
At each position:
1. TRY: all possible cuts from this position
2. CHECK: is the substring a palindrome?
3. CHOOSE: if YES, add it to current partition
4. EXPLORE: recursively partition the rest
5. UNCHOOSE: remove what we added (backtrack)
6. COLLECT: when we reach the end, save the partition
This is the classic "Choose-Explore-Unchoose" pattern!
📝 Implementation
class Solution {
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) {
// Base case: reached end of string
if (start == s.length()) {
result.add(new ArrayList<>(current)); // Save this partition
return;
}
// Try all possible cuts from current position
for (int end = start; end < s.length(); end++) {
// Check if substring from start to end is palindrome
if (isPalindrome(s, start, end)) {
// CHOOSE: Add this palindrome to current partition
current.add(s.substring(start, end + 1));
// EXPLORE: Recursively partition the rest
backtrack(s, end + 1, current, result);
// UNCHOOSE: Remove last added (backtrack)
current.remove(current.size() - 1);
}
}
}
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}
🔍 Detailed Dry Run: s = "aabb"
backtrack("aabb", 0, [], result)
│
├─ Try cut at position 0 (substring "a")
│ ├─ isPalindrome("aabb", 0, 0) → "a" → TRUE ✓
│ ├─ current = ["a"]
│ ├─ backtrack("aabb", 1, ["a"], result)
│ │ │
│ │ ├─ Try cut at position 1 (substring "a")
│ │ │ ├─ isPalindrome("aabb", 1, 1) → "a" → TRUE ✓
│ │ │ ├─ current = ["a", "a"]
│ │ │ ├─ backtrack("aabb", 2, ["a","a"], result)
│ │ │ │ │
│ │ │ │ ├─ Try cut at position 2 (substring "b")
│ │ │ │ │ ├─ isPalindrome("aabb", 2, 2) → "b" → TRUE ✓
│ │ │ │ │ ├─ current = ["a", "a", "b"]
│ │ │ │ │ ├─ backtrack("aabb", 3, ["a","a","b"], result)
│ │ │ │ │ │ │
│ │ │ │ │ │ ├─ Try cut at position 3 (substring "b")
│ │ │ │ │ │ │ ├─ isPalindrome("aabb", 3, 3) → "b" → TRUE ✓
│ │ │ │ │ │ │ ├─ current = ["a", "a", "b", "b"]
│ │ │ │ │ │ │ ├─ backtrack("aabb", 4, ["a","a","b","b"], result)
│ │ │ │ │ │ │ │ └─ start == length → FOUND PARTITION!
│ │ │ │ │ │ │ │ result.add(["a","a","b","b"]) ✓
│ │ │ │ │ │ │ └─ UNCHOOSE: current = ["a", "a", "b"]
│ │ │ │ │ │ └─ return
│ │ │ │ │ └─ UNCHOOSE: current = ["a", "a"]
│ │ │ │ │
│ │ │ │ ├─ Try cut at position 2-3 (substring "bb")
│ │ │ │ │ ├─ isPalindrome("aabb", 2, 3) → "bb" → TRUE ✓
│ │ │ │ │ ├─ current = ["a", "a", "bb"]
│ │ │ │ │ ├─ backtrack("aabb", 4, ["a","a","bb"], result)
│ │ │ │ │ │ └─ start == length → FOUND PARTITION!
│ │ │ │ │ │ result.add(["a","a","bb"]) ✓
│ │ │ │ │ └─ UNCHOOSE: current = ["a", "a"]
│ │ │ │ └─ return
│ │ │ └─ UNCHOOSE: current = ["a"]
│ │ │
│ │ ├─ Try cut at position 1-2 (substring "ab")
│ │ │ ├─ isPalindrome("aabb", 1, 2) → "ab" → FALSE ✗
│ │ │ └─ Skip this cut
│ │ │
│ │ ├─ Try cut at position 1-3 (substring "abb")
│ │ │ ├─ isPalindrome("aabb", 1, 3) → "abb" → FALSE ✗
│ │ │ └─ Skip this cut
│ │ └─ return
│ └─ UNCHOOSE: current = []
│
├─ Try cut at position 0-1 (substring "aa")
│ ├─ isPalindrome("aabb", 0, 1) → "aa" → TRUE ✓
│ ├─ current = ["aa"]
│ ├─ backtrack("aabb", 2, ["aa"], result)
│ │ │
│ │ ├─ Try cut at position 2 (substring "b")
│ │ │ ├─ isPalindrome("aabb", 2, 2) → "b" → TRUE ✓
│ │ │ ├─ current = ["aa", "b"]
│ │ │ ├─ backtrack("aabb", 3, ["aa","b"], result)
│ │ │ │ │
│ │ │ │ ├─ Try cut at position 3 (substring "b")
│ │ │ │ │ ├─ isPalindrome("aabb", 3, 3) → "b" → TRUE ✓
│ │ │ │ │ ├─ current = ["aa", "b", "b"]
│ │ │ │ │ ├─ backtrack("aabb", 4, ["aa","b","b"], result)
│ │ │ │ │ │ └─ start == length → FOUND PARTITION!
│ │ │ │ │ │ result.add(["aa","b","b"]) ✓
│ │ │ │ │ └─ UNCHOOSE: current = ["aa", "b"]
│ │ │ │ └─ return
│ │ │ └─ UNCHOOSE: current = ["aa"]
│ │ │
│ │ ├─ Try cut at position 2-3 (substring "bb")
│ │ │ ├─ isPalindrome("aabb", 2, 3) → "bb" → TRUE ✓
│ │ │ ├─ current = ["aa", "bb"]
│ │ │ ├─ backtrack("aabb", 4, ["aa","bb"], result)
│ │ │ │ └─ start == length → FOUND PARTITION!
│ │ │ │ result.add(["aa","bb"]) ✓
│ │ │ └─ UNCHOOSE: current = ["aa"]
│ │ └─ return
│ └─ UNCHOOSE: current = []
│
├─ Try cut at position 0-2 (substring "aab")
│ ├─ isPalindrome("aabb", 0, 2) → "aab" → FALSE ✗
│ └─ Skip this cut
│
├─ Try cut at position 0-3 (substring "aabb")
│ ├─ isPalindrome("aabb", 0, 3) → "aabb" → FALSE ✗
│ └─ Skip this cut
│
└─ Final result = [
["a","a","b","b"],
["a","a","bb"],
["aa","b","b"],
["aa","bb"]
]
Total: 4 valid partitions found! ✓
Counting Palindrome Checks:
Notice how many times we check palindromes:
"a" (index 0-0): checked once
"a" (index 1-1): checked once
"aa" (index 0-1): checked once
"ab" (index 1-2): checked once
"aab" (index 0-2): checked once
"abb" (index 1-3): checked once
"aabb" (index 0-3): checked once
"b" (index 2-2): checked TWICE! ⚠️
"b" (index 3-3): checked TWICE! ⚠️
"bb" (index 2-3): checked TWICE! ⚠️
Some substrings checked multiple times!
This is inefficient but works correctly.
📊 Complexity Analysis
Time Complexity: O(n × 2^n)
At each position, we decide: cut here or don't cut
This creates 2^n possible partition combinations
For each partition:
- Extract substrings: O(n)
- Check palindromes: O(n) per check, multiple checks
Total: O(n × 2^n) for exploring all partitions
Plus: Repeated palindrome checks add overhead
Space Complexity: O(n)
Recursion depth: O(n) worst case
Current partition storage: O(n)
Total: O(n)
The Problem:
✅ Finds all valid partitions correctly
✅ Logic is straightforward
❌ Checks same substrings for palindrome multiple times
❌ Inefficient for larger strings
🔄 Can optimize with DP precomputation!
🟡 Approach 2: Backtracking + Top-Down DP (Memoized Palindrome Checks)
📐 Function Definition
Function Signature:
void backtrack(String s, int start, List<String> current,
List<List<String>> result, Boolean[][] dp)
boolean isPalindrome(String s, int left, int right, Boolean[][] dp)
What it represents:
Input Parameter dp (Boolean[][]):
- Memoization table for palindrome results
- dp[i][j] = is substring s[i..j] a palindrome?
- null = not yet checked
- true = is palindrome
- false = not palindrome
Purpose: - Same backtracking as Approach 1 - BUT cache palindrome check results - Avoid checking same substring twice
Key Understanding:
First time checking s[2..3] = "bb":
- dp[2][3] = null (not checked yet)
- Calculate: 'b' == 'b' → true
- Store: dp[2][3] = true
- Return: true
Second time checking s[2..3] = "bb":
- dp[2][3] = true (already know!)
- Return immediately: true
- No recalculation needed! ✨
💡 Intuition
The idea is simple: Don't check the same thing twice!
OBSERVATION:
In Approach 1, we checked "bb" twice
We checked "b" twice at different positions
This is wasteful!
SOLUTION:
First time we check a substring:
- Calculate if it's palindrome
- Remember the result in dp[i][j]
Next time we need same substring:
- Look up dp[i][j]
- Return immediately
- No recalculation! 🚀
This is "memoization" - remember results to avoid recomputation!
📝 Implementation
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
Boolean[][] dp = new Boolean[s.length()][s.length()];
backtrack(s, 0, new ArrayList<>(), result, dp);
return result;
}
private void backtrack(String s, int start, List<String> current,
List<List<String>> result, Boolean[][] dp) {
if (start == s.length()) {
result.add(new ArrayList<>(current));
return;
}
for (int end = start; end < s.length(); end++) {
// Check palindrome with memoization
if (isPalindrome(s, start, end, dp)) {
current.add(s.substring(start, end + 1));
backtrack(s, end + 1, current, result, dp);
current.remove(current.size() - 1);
}
}
}
private boolean isPalindrome(String s, int left, int right, Boolean[][] dp) {
// Check if already calculated
if (dp[left][right] != null) {
return dp[left][right]; // Return cached result!
}
// Base cases
if (left >= right) {
dp[left][right] = true;
return true;
}
// Calculate and store
if (s.charAt(left) == s.charAt(right)) {
dp[left][right] = isPalindrome(s, left + 1, right - 1, dp);
} else {
dp[left][right] = false;
}
return dp[left][right];
}
}
📊 Complexity Analysis
Time Complexity: O(n × 2^n)
Same backtracking complexity
But palindrome checks are now O(1) after first check!
Much faster in practice!
Space Complexity: O(n²)
DP table: O(n²) to store all substring results
Recursion: O(n)
Total: O(n²)
🟢 Approach 3: Backtracking + Bottom-Up DP (Precomputed Palindrome Table)
📐 Function Definition
DP Array Definition:
boolean[][] dp = new boolean[n][n];
What dp[i][j] represents:
Indices i and j:
- Substring boundaries in the string
- dp[i][j] represents s[i..j]
- Example: dp[0][1] represents s[0..1] = "aa" in "aabb"
Value dp[i][j] (boolean):
- true = substring s[i..j] IS a palindrome
- false = substring s[i..j] is NOT a palindrome
Purpose: - Build COMPLETE palindrome table BEFORE backtracking - Then use O(1) lookups during backtracking - No recursive palindrome checking needed!
Key Understanding:
For "aabb", the complete table tells us:
dp[0][0] = true → "a" is palindrome
dp[0][1] = true → "aa" is palindrome
dp[0][2] = false → "aab" is NOT palindrome
dp[0][3] = false → "aabb" is NOT palindrome
dp[1][1] = true → "a" is palindrome
dp[1][2] = false → "ab" is NOT palindrome
dp[1][3] = false → "abb" is NOT palindrome
dp[2][2] = true → "b" is palindrome
dp[2][3] = true → "bb" is palindrome
dp[3][3] = true → "b" is palindrome
Build this once, use many times!
💡 Intuition
The most intuitive approach: Know all palindromes upfront, then explore partitions!
Think of it like solving a puzzle:
PREPARATION PHASE:
Before starting the puzzle, organize all pieces
Check which substrings are palindromes
Store this info in a table
SOLUTION PHASE:
Now solve the puzzle using the organized info
At each step, instantly know if a piece fits (palindrome check)
No need to verify each time!
This is the CLEANEST approach:
1. Build palindrome table (DP)
2. Use table for backtracking
Clear separation of concerns! 🎯
How to Build the Palindrome Table:
Key insight: Build by increasing length!
Length 1: All single characters are palindromes
dp[0][0] = true ("a")
dp[1][1] = true ("a")
dp[2][2] = true ("b")
dp[3][3] = true ("b")
Length 2: Two chars palindrome if they're equal
dp[0][1] = (s[0] == s[1]) = ('a' == 'a') = true ("aa")
dp[1][2] = (s[1] == s[2]) = ('a' == 'b') = false ("ab")
dp[2][3] = (s[2] == s[3]) = ('b' == 'b') = true ("bb")
Length 3: Check ends equal AND inner is palindrome
dp[0][2] = (s[0] == s[2]) AND dp[1][1]
= ('a' == 'b') = false ("aab")
dp[1][3] = (s[1] == s[3]) AND dp[2][2]
= ('a' == 'b') = false ("abb")
Length 4: Check ends equal AND inner is palindrome
dp[0][3] = (s[0] == s[3]) AND dp[1][2]
= ('a' == 'b') = false ("aabb")
Building by length ensures inner palindromes are ready!
🎯 Base Cases Transformation
Why build by length?
For dp[i][j], we need to know dp[i+1][j-1]
(Inner substring must be checked first!)
Example: To know if "aabb" is palindrome
Need to know: s[0] == s[3]? ('a' == 'b'? NO)
Also need: Is inner "ab" palindrome? (dp[1][2])
So dp[1][2] must be computed BEFORE dp[0][3]!
Building by increasing length guarantees this!
Length 1 → Length 2 → Length 3 → Length 4
This way, all dependencies are satisfied! 🎯
📝 Implementation
class Solution {
public List<List<String>> partition(String s) {
int n = s.length();
// PHASE 1: Build palindrome table
boolean[][] dp = new boolean[n][n];
for (int length = 1; length <= n; length++) {
for (int i = 0; i <= n - length; i++) {
int j = i + length - 1;
if (length == 1) {
// Single character - always palindrome
dp[i][j] = true;
} else if (length == 2) {
// Two characters - palindrome if equal
dp[i][j] = (s.charAt(i) == s.charAt(j));
} else {
// Longer substring - check ends AND inner
dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i + 1][j - 1];
}
}
}
// PHASE 2: Backtrack using precomputed table
List<List<String>> result = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), result, dp);
return result;
}
private void backtrack(String s, int start, List<String> current,
List<List<String>> result, boolean[][] dp) {
if (start == s.length()) {
result.add(new ArrayList<>(current));
return;
}
for (int end = start; end < s.length(); end++) {
// O(1) palindrome lookup!
if (dp[start][end]) {
current.add(s.substring(start, end + 1));
backtrack(s, end + 1, current, result, dp);
current.remove(current.size() - 1);
}
}
}
}
🔍 Detailed Dry Run: s = "aabb"
Input: s = "aabb", n = 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PHASE 1: BUILD PALINDROME TABLE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Initial empty table:
0 1 2 3
0 [ ? ][ ? ][ ? ][ ? ]
1 [ ? ][ ? ][ ? ]
2 [ ? ][ ? ]
3 [ ? ]
Length 1 (single characters):
━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=0, j=0: s[0]='a' → dp[0][0] = true
i=1, j=1: s[1]='a' → dp[1][1] = true
i=2, j=2: s[2]='b' → dp[2][2] = true
i=3, j=3: s[3]='b' → dp[3][3] = true
0 1 2 3
0 [ T ][ ? ][ ? ][ ? ]
1 [ T ][ ? ][ ? ]
2 [ T ][ ? ]
3 [ T ]
Length 2 (two characters):
━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=0, j=1: s[0]='a', s[1]='a' → equal → dp[0][1] = true ✓
i=1, j=2: s[1]='a', s[2]='b' → NOT equal → dp[1][2] = false ✗
i=2, j=3: s[2]='b', s[3]='b' → equal → dp[2][3] = true ✓
0 1 2 3
0 [ T ][ T ][ ? ][ ? ]
1 [ T ][ F ][ ? ]
2 [ T ][ T ]
3 [ T ]
Length 3 (three characters):
━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=0, j=2: s[0]='a', s[2]='b' → NOT equal → dp[0][2] = false ✗
i=1, j=3: s[1]='a', s[3]='b' → NOT equal → dp[1][3] = false ✗
0 1 2 3
0 [ T ][ T ][ F ][ ? ]
1 [ T ][ F ][ F ]
2 [ T ][ T ]
3 [ T ]
Length 4 (four characters):
━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=0, j=3: s[0]='a', s[3]='b' → NOT equal → dp[0][3] = false ✗
Final palindrome table:
0 1 2 3
0 [ T ][ T ][ F ][ F ] ← "a", "aa", "aab", "aabb"
1 [ T ][ F ][ F ] ← "a", "ab", "abb"
2 [ T ][ T ] ← "b", "bb"
3 [ T ] ← "b"
Reading the table:
dp[0][0] = true → "a" is palindrome ✓
dp[0][1] = true → "aa" is palindrome ✓
dp[0][2] = false → "aab" is NOT palindrome ✗
dp[0][3] = false → "aabb" is NOT palindrome ✗
dp[1][1] = true → "a" is palindrome ✓
dp[1][2] = false → "ab" is NOT palindrome ✗
dp[1][3] = false → "abb" is NOT palindrome ✗
dp[2][2] = true → "b" is palindrome ✓
dp[2][3] = true → "bb" is palindrome ✓
dp[3][3] = true → "b" is palindrome ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PHASE 2: BACKTRACKING (Using Precomputed Table)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
backtrack(0, [])
Check dp[0][0]=true → Add "a"
backtrack(1, ["a"])
Check dp[1][1]=true → Add "a"
backtrack(2, ["a","a"])
Check dp[2][2]=true → Add "b"
backtrack(3, ["a","a","b"])
Check dp[3][3]=true → Add "b"
backtrack(4, ["a","a","b","b"])
Reached end → Add ["a","a","b","b"] to result ✓
Check dp[2][3]=true → Add "bb"
backtrack(4, ["a","a","bb"])
Reached end → Add ["a","a","bb"] to result ✓
Check dp[0][1]=true → Add "aa"
backtrack(2, ["aa"])
Check dp[2][2]=true → Add "b"
backtrack(3, ["aa","b"])
Check dp[3][3]=true → Add "b"
backtrack(4, ["aa","b","b"])
Reached end → Add ["aa","b","b"] to result ✓
Check dp[2][3]=true → Add "bb"
backtrack(4, ["aa","bb"])
Reached end → Add ["aa","bb"] to result ✓
Check dp[0][2]=false → Skip "aab"
Check dp[0][3]=false → Skip "aabb"
Final result: [
["a","a","b","b"],
["a","a","bb"],
["aa","b","b"],
["aa","bb"]
]
Total: 4 valid partitions found! ✓
Why This Is The Best Approach:
ADVANTAGES:
✅ Clear two-phase structure
✅ All palindrome checks are O(1)
✅ No repeated palindrome calculations
✅ Easy to understand and debug
✅ Optimal time complexity
EFFICIENCY:
Palindrome table: Built once in O(n²)
Backtracking: Uses O(1) lookups
Total: O(n²) prep + O(n × 2^n) backtracking
This is THE standard solution! 🏆
📊 Complexity Analysis
Time Complexity: O(n² + n × 2^n)
Build palindrome table: O(n²)
- All substrings: n(n+1)/2 ≈ n²
- Each cell: O(1) using previous results
Backtracking: O(n × 2^n)
- Number of partitions: O(2^n)
- Work per partition: O(n)
Total: O(n²) + O(n × 2^n) = O(n × 2^n)
Space Complexity: O(n²)
DP table: O(n²) - all substring palindrome info
Recursion stack: O(n)
Current partition: O(n)
Total: O(n²)
🔵 Approach 4: Space-Optimized (No DP Table)
💡 Intuition
For small strings (n ≤ 16), the O(n²) table might be overkill:
Trade-off decision:
- DP table saves time but uses O(n²) space
- For n=16: 16² = 256 cells
- For small n, repeated checks are fast enough
Space-optimized approach:
- Check palindromes on-demand (like Approach 1)
- No memoization table
- Save O(n²) space
- Good for memory-constrained environments
📝 Implementation
class Solution {
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));
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);
}
}
}
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}
📊 Complexity Analysis
Time Complexity: O(n × 2^n)
Slightly slower due to repeated palindrome checks
But for n ≤ 16, difference is negligible
Space Complexity: O(n)
No DP table: Best space complexity!
Only recursion stack: O(n)
🎯 Pattern Recognition
Core Pattern: Generate All Valid Combinations
When you need to find ALL valid ways to do something:
1. Use BACKTRACKING to explore all possibilities
2. Use DP to optimize expensive checks
3. Use Choose-Explore-Unchoose pattern
For Palindrome Partitioning:
- BACKTRACKING: Try all partition points
- DP: Precompute palindrome information
- PATTERN: Choose cut → Explore rest → Unchoose
⚠️ Important Edge Cases to Test
s = "a" // Expected: [["a"]]
s = "aaa" // Expected: [["a","a","a"],["a","aa"],["aa","a"],["aaa"]]
s = "ab" // Expected: [["a","b"]]
s = "aba" // Expected: [["a","b","a"],["aba"]]
s = "aab" // Expected: [["a","a","b"],["aa","b"]]
s = "aabb" // Expected: [["a","a","b","b"],["a","a","bb"],["aa","b","b"],["aa","bb"]]
s = "abba" // Expected: [["a","b","b","a"],["a","bb","a"],["abba"]]
s = "racecar" // Expected: Multiple including ["racecar"]
📝 Quick Revision Notes
🎯 Core Concept
Problem: Partition string so every piece is palindrome. Return ALL valid partitions.
Key Insight: Two-phase approach = Build palindrome table (DP), then backtrack with O(1) lookups.
Four Approaches: 1. Backtracking Only → O(n × 2^n), O(n) space, repeated checks 2. Memoized Checks → O(n × 2^n), O(n²) space, cached checks 3. Precomputed Table → O(n × 2^n), O(n²) space, best! ⭐ 4. Space-Optimized → O(n × 2^n), O(n) space, for small n
⚡ Quick Implementation
https://www.youtube.com/watch?v=WBgsABoClE0
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<List<String>> partition(String s) {
int n = s.length();
List<List<String>> res = new ArrayList<>();
// // Approach 1 - recursive
// recursive(s, n, 0, new ArrayList<>(), res);
// // Approach 2 - top down
// // GOTCHA: Optimization will happen while checking if string
// // is palindrome or not. Nowhere else. That is the main
// // confusion of this problem.
// Boolean[][] memo = new Boolean[n][n];
// topDown(s, n, 0, new ArrayList<>(), res, memo);
bottomUp(s, res);
return res;
}
private void bottomUp(String s, List<List<String>> res) {
int n = s.length();
// Build the palindrome DP table first.
// 3 cases - 1 length, 2 length and remaining lengths
boolean[][] dp = new boolean[n][n];
// GOTCHA: see the reverse of i loop.
// Since its dp[i+1][j-1], i should come from end j should start from 0
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (i == j) {
dp[i][j] = true;
} else if (j == i + 1) {
dp[i][j] = s.charAt(i) == s.charAt(j);
} else {
dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i + 1][j - 1];
}
}
}
recursive(s, n, 0, new ArrayList<>(), res, dp);
}
private void recursive(String s, int n, int start, ArrayList<String> curr, List<List<String>> res,
boolean[][] dp) {
// step 2: base case
if (start == n) {
res.add(new ArrayList<>(curr));
return;
}
for (int end = start; end < n; end++) {
if (dp[start][end]) {
curr.add(s.substring(start, end + 1));
recursive(s, n, end + 1, curr, res, dp);
curr.remove(curr.size() - 1);
}
}
}
private void topDown(String s, int n, int start, ArrayList<String> curr, List<List<String>> res, Boolean[][] memo) {
if (start == n) {
res.add(new ArrayList<>(curr));
}
for (int end = start; end < n; end++) {
if (isPalindrome(s, start, end, memo)) {
curr.add(s.substring(start, end + 1));
// for a|abb => we now proceed for abb
// for aa|bb => we now proceed for bb
topDown(s, n, end + 1, curr, res, memo);
// why remove? above call will build the result like aa, bb
curr.remove(curr.size() - 1);
}
}
}
private boolean isPalindrome(String s, int start, int end, Boolean[][] memo) {
if (memo[start][end] != null) {
return memo[start][end];
}
if (start >= end) {
return true;
}
while (start <= end) {
if (s.charAt(start) != s.charAt(end)) {
return memo[start][end] = false;
}
start++;
end--;
}
return memo[start][end] = true;
}
private void recursive(String s, int n, int start, ArrayList<String> curr, List<List<String>> res) {
// step 2: base case
if (start == n) {
res.add(new ArrayList<>(curr));
return;
}
// step 1: cut at every index start from index
// for start = 0, end traverses from end = 0 to end = n - 1
// aabb => a|abb, aa|bb, aab|b, aabb
// check if every cut is a palindrome. If yes, then only proceed to next.
// for example, a|abb => a is a palindrome. Now, repeat the cycle for abb
// For aa|bb => aa is a palindrome. Now, repeat the cycle for bb
// aab is not a palindrome. Do not proceed
// aabb is a palindome. Add it to the result.
for (int end = start; end < n; end++) {
if (isPalindrome(s, start, end)) {
curr.add(s.substring(start, end + 1));
// for a|abb => we now proceed for abb
// for aa|bb => we now proceed for bb
recursive(s, n, end + 1, curr, res);
// why remove? above call will build the result like aa, bb
curr.remove(curr.size() - 1);
}
}
}
private boolean isPalindrome(String s, int start, int end) {
while (start <= end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
public static void main(String[] args) {
Solution s = new Solution();
// [[a, a, b, b], [a, a, bb], [aa, b, b], [aa, bb]]
System.out.println(s.partition("aabb"));
System.out.println(s.partition("a")); // [[a]]
// [["a","a","a"],["a","aa"],["aa","a"],["aaa"]]
System.out.println(s.partition("aaa"));
System.out.println(s.partition("ab")); // [["a","b"]]
System.out.println(s.partition("aba")); // [["a","b","a"],["aba"]]
System.out.println(s.partition("aab")); // [["a","a","b"],["aa","b"]]
// [["a","b","b","a"],["a","bb","a"],["abba"]]
System.out.println(s.partition("abba"));
}
}
🔑 Key Insights
Why Build by Length:
dp[i][j] needs dp[i+1][j-1] (inner substring)
Building by length ensures inner is ready:
Length 1 → Length 2 → Length 3 → ...
Each length uses only previous lengths!
Choose-Explore-Unchoose:
current.add(substring) // Choose
backtrack(next_position) // Explore
current.remove(current.size()-1) // Unchoose
This pattern naturally explores all combinations!
Why Create Copy:
result.add(new ArrayList<>(current)) // CORRECT ✓
result.add(current) // WRONG ✗
Must create copy! Otherwise all results
point to same list that keeps changing!
🎪 Memory Aid
"Build table first, backtrack second!"
"Choose-Explore-Unchoose pattern!"
"Build by length, inner first!"
"Always copy when adding to result!" ✨
⚠️ Common Mistakes
- ❌ Not creating copy when adding to result
- ❌ Forgetting to backtrack (remove last element)
- ❌ Building palindrome table in wrong order
- ❌ Checking palindrome without any optimization
- ❌ Off-by-one errors in substring indices
🎉 Congratulations!
You've mastered Palindrome Partitioning with the "aabb" example!
What You Learned:
✅ Generation Problems - Finding ALL solutions
✅ Two-Phase Approach - DP + Backtracking
✅ Palindrome Table - Build by length
✅ Backtracking Pattern - Choose-Explore-Unchoose
✅ Space-Time Tradeoff - When to use DP table
You've mastered combining DP with Backtracking! 🚀✨