Matrix Chain Multiplication had matrices and multiplication costs. Palindrome Partitioning has a string and cuts. The problems look nothing alike. But once you map the structure, the skeleton is identical and only tempAns changes.
The Problem
Given a string, partition it so that every substring in the partition is a palindrome. Find the minimum number of cuts needed.
s = "NITIK"
Trivial partition: N | I | T | I | K → 4 cuts (valid but not minimal)
Optimal partition: N | ITI | K → 2 cuts
N → palindrome ✓
ITI → palindrome ✓
K → palindrome ✓
Answer: 2
Every individual character is a palindrome, so you can always cut the string into single characters. But that's the worst case. You want to find where cutting fewer times still gives all palindromes.
Recognising the MCM Pattern
From Chapter 1, the four signals are: array or string, can be partitioned, minimum answer needed, multiple partition points possible.
String: NITIK
Partitions: N | ITIK
NI | TIK
NIT | IK
NITI | K
Minimum answer: yes
Multiple k: yes
All four signals are present. This is an MCM problem.
The same (i, j, k) structure applies. i is the left boundary, j is the right boundary, k is the split point. solve(i, j) is the minimum cuts for s[i..j].
The Base Cases
Two things can end the recursion early.
i >= j: A single character or an empty range. One character is always a palindrome. No cuts needed. Return 0.
The entire substring s[i..j] is already a palindrome: No need to partition it at all. Return 0.
if i >= j:
return 0
if isPalindrome(s, i, j):
return 0
The isPalindrome check is an extra base case that doesn't exist in MCM. It's a short-circuit: if the current range is already palindromic, don't cut it further.
The tempAns Line
After the base cases, try every k from i to j-1. Split the string at k and compute the cost of each partition.
solve(i, k) → minimum cuts for left substring s[i..k]
solve(k+1, j) → minimum cuts for right substring s[k+1..j]
+1 → the cut at position k that separates the two halves
tempAns = solve(i, k) + solve(k + 1, j) + 1
ans = min(ans, tempAns)
Compare with MCM:
MCM: solve(i,k) + solve(k+1,j) + arr[i-1]*arr[k]*arr[j]
Palindrome: solve(i,k) + solve(k+1,j) + 1
The +1 replaces the multiplication cost. Everything else is the same.
The Helper Function
def isPalindrome(s, i, j):
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
This runs in O(n) per call. For each (i, j) pair and each value of k, isPalindrome is called on the initial range once. It's not called on each subproblem — the base case check only applies to the top-level call for each (i, j).
The Recursive Solution
class Solution:
def isPalindrome(self, s, i, j):
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
def solve(self, s, i, j):
# Base case: single char or empty range
if i >= j:
return 0
# Short-circuit: no cuts needed if already palindrome
if self.isPalindrome(s, i, j):
return 0
ans = float('inf')
for k in range(i, j):
# Cut at k: left + right + 1 cut
tempAns = (
self.solve(s, i, k)
+ self.solve(s, k + 1, j)
+ 1
)
ans = min(ans, tempAns)
return ans
def minCut(self, s):
return self.solve(s, 0, len(s) - 1)
Adding Memoization
Same reasoning as MCM. The state is (i, j). Initialise with -1. Check before computing, store after.
class Solution:
def isPalindrome(self, s, i, j):
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
def minCut(self, s):
n = len(s)
T = [[-1] * n for _ in range(n)]
def solve(i, j):
if i >= j:
return 0
if self.isPalindrome(s, i, j):
return 0
# Return stored answer if already computed
if T[i][j] != -1:
return T[i][j]
ans = float('inf')
for k in range(i, j):
# Use cached values where available
left = T[i][k] if T[i][k] != -1 else solve(i, k)
right = T[k+1][j] if T[k+1][j] != -1 else solve(k+1, j)
if T[i][k] == -1: T[i][k] = left
if T[k+1][j] == -1: T[k+1][j] = right
tempAns = 1 + left + right
ans = min(ans, tempAns)
T[i][j] = ans
return ans
return solve(0, n - 1)
MCM vs Palindrome Partitioning
| MCM | Palindrome Partitioning | |
|---|---|---|
| Input | Dimension array | String |
solve(i,j) means |
Min multiplication cost | Min cuts |
k loop |
range(i, j) |
range(i, j) |
| Left subproblem | solve(i, k) |
solve(i, k) |
| Right subproblem | solve(k+1, j) |
solve(k+1, j) |
tempAns |
left + right + arr[i-1]*arr[k]*arr[j] |
left + right + 1 |
| Extra base case | None | isPalindrome(s, i, j) |
| Aggregation | min |
min |
| Memoised state | (i, j) |
(i, j) |
The rows that differ: tempAns and the extra palindrome base case. Every other row is identical.
Quick Revision
solve(i, j) = minimum cuts for s[i..j]
Base cases:
if i >= j: return 0
if isPalindrome(s, i, j): return 0
Transition:
for k in range(i, j):
tempAns = solve(i,k) + solve(k+1,j) + 1
ans = min(ans, tempAns)
Memoize: T[i][j], initialised to -1
Initial call: solve(0, n-1)
The only change from MCM:
tempAns uses +1 instead of arr[i-1]*arr[k]*arr[j]
Extra isPalindrome base case
What You Now Understand
Palindrome Partitioning is MCM with a simpler tempAns. The combining cost of splitting a string at position k is just +1 — the single cut that divides the two halves. The isPalindrome check is an optimisation that short-circuits the recursion when the current range needs no further cutting.
The next chapter applies the same skeleton to Boolean Parenthesization, where the tempAns becomes more involved: instead of counting cuts or multiplications, you're counting how many ways to parenthesise a boolean expression so that it evaluates to True. The structure is the same. The combination logic is where things get interesting.
Top comments (0)