Palindrome Partitioning II
Combine a precomputed palindrome table with 1D DP to find the minimum cuts needed to partition a string into palindromes.
Palindrome Partitioning II is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Problem: Minimum Cuts to Partition
Palindrome Partitioning II asks: given string s, find the minimum number of cuts so that every substring in the partition is a palindrome. For 'aab', one cut gives ['aa', 'b'], so the answer is 1. For 'a' the answer is 0 (already a palindrome). This problem combines two DP phases: first precompute which substrings are palindromes, then use 1D DP to find minimum cuts.
Phase 1: Precompute Palindrome Table
First build is_pal[i][j] = True if s[i..j] is a palindrome using interval DP. This runs in O(n²) time and O(n²) space. Alternatively, expand-around-centre fills the same table in O(n²) time. We need this table because the 1D cut DP will query is_pal[i][j] repeatedly — precomputing avoids recomputing palindrome checks inside the cut DP loop.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
print(build_palindrome_table('aab'))Phase 2: 1D Cut DP Setup
Define cuts[i] as the minimum cuts to partition s[0..i]. If s[0..i] is itself a palindrome, cuts[i] = 0. Otherwise, try every split: for each j from 0 to i-1, if s[j+1..i] is a palindrome, then cuts[i] = min(cuts[i], cuts[j] + 1). We are asking: what if the last partition piece is s[j+1..i]? Then we need cuts[j] cuts for the prefix plus 1 more cut.
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0 # entire prefix is a palindrome
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]Full Solution and Trace
Let's trace through 'aab'. Palindrome table: is_pal[0][0]='a'=T, is_pal[1][1]='a'=T, is_pal[2][2]='b'=T, is_pal[0][1]='aa'=T, is_pal[1][2]='ab'=F, is_pal[0][2]='aab'=F. Cuts: cuts[0]=0 ('a' is palindrome), cuts[1]=0 ('aa' is palindrome), cuts[2]: 'aab' not palindrome, try j=1: is_pal[2][2]=T so cuts[2] = cuts[1]+1 = 1. Answer: 1.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]
print(min_cut('aab')) # 1
print(min_cut('ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab'))Time and Space Complexity
Phase 1 (palindrome table) runs in O(n²) time and O(n²) space. Phase 2 (cut DP) has an outer loop over n positions and an inner loop over n split points, also O(n²) time. Overall: O(n²) time, O(n²) space. The space can be reduced to O(n) for the cuts array, but the palindrome table still requires O(n²). Interviewers expect O(n²) — an O(n) solution using Manacher's is beyond typical scope.
Expand-Around-Centre for Palindrome Table
Instead of the interval DP approach for the palindrome table, you can fill is_pal using expand-around-centre. For each centre position, expand outward and mark all palindromes found. This is still O(n²) time and O(n²) space, but may be faster in practice due to better cache behaviour. Both approaches are valid in interviews.
def build_pal_expand(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
def expand(l, r):
while l >= 0 and r < n and s[l] == s[r]:
is_pal[l][r] = True
l -= 1; r += 1
for i in range(n):
expand(i, i) # odd-length centres
expand(i, i+1) # even-length centres
return is_pal
print('Expand-around-centre palindrome table built')Enumerating All Partitions (Part I)
Palindrome Partitioning I (a related problem) asks to enumerate ALL valid partitions where every substring is a palindrome. This uses backtracking with the precomputed palindrome table as a pruning oracle. Unlike the minimum-cuts DP which counts, this enumerates exponentially many solutions and is solved with a different approach entirely.
def partition_all(s):
n = len(s)
is_pal = build_pal_expand(s)
result = []
def backtrack(start, path):
if start == n:
result.append(path[:])
return
for end in range(start, n):
if is_pal[start][end]:
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
backtrack(0, [])
return result
print(partition_all('aab')) # [['a','a','b'], ['aa','b']]Initialising cuts with n-1
A common trick: initialise cuts[i] = i instead of inf, since the worst case for s[0..i] is to cut every character separately, giving i cuts. This avoids checking for inf in your code. When is_pal[0][i] is true, we override with 0. This initialisation clarifies the upper bound on cuts and simplifies the code slightly.
def min_cut_clean(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n)) # cuts[i] = i (worst case)
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]Alternative: One-Pass DP Without Separate Table
An elegant variant fills the palindrome table and cut DP simultaneously. As we expand palindromes from each centre, we immediately update the cuts array. For a palindrome s[l..r], we can update cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0)). This avoids a separate O(n²) table pass and may be cleaner to implement during an interview under time pressure.
Edge Cases to Consider
Key edge cases for palindrome partitioning II: (1) single-character string returns 0 cuts; (2) string that is already a palindrome returns 0 cuts; (3) string of all distinct characters needs n-1 cuts; (4) string of all identical characters (e.g., 'aaaa') needs 0 cuts since the whole string is a palindrome. Always verify your solution handles the is_pal[0][i] = True early-exit correctly.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n))
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]
print(min_cut('a')) # 0
print(min_cut('aaaa')) # 0
print(min_cut('abc')) # 2Interview Communication Tips
When presenting this problem in an interview, lead with the two-phase approach: first build the palindrome table, then run 1D DP on the cuts array. Explain the recurrence verbally before coding. Mention that the palindrome table has O(n²) entries and each is filled in O(1) using the interval DP recurrence. Always walk through your trace example before writing the full solution to demonstrate correctness under pressure.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: palindrome partitioning II uses two DP phases — precompute palindrome table then run 1D cut DP, the cut recurrence is cuts[i] = min(cuts[j-1] + 1) for all j where s[j..i] is a palindrome, and the overall complexity is O(n²) time and O(n²) space. Next up we tackle the Burst Balloons problem, which uses a clever reverse interval DP approach.
Frequently asked questions
Is the “Palindrome Partitioning II” lesson free?
Yes — the full text of “Palindrome Partitioning II” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Palindrome Partitioning II”?
Combine a precomputed palindrome table with 1D DP to find the minimum cuts needed to partition a string into palindromes. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Palindrome Partitioning II” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.