Practice › Dynamic Programming
Palindrome Partitioning II
Hard · Dynamic Programming · Asked at Amazon, Google, Microsoft
Cut the string into pieces so that every piece is a palindrome. Print the minimum number of cuts needed.
Input
A single lowercase string s.
Output
The minimum number of cuts.
Constraints
- 1 ≤ |s| ≤ 2000
Precompute isPal[i][j]. Then cuts[i] (for prefix s[0..i]) = 0 if the whole prefix is a palindrome, else min over j of cuts[j−1] + 1 where s[j..i] is a palindrome.
Example 1
Input
aab
Output
1
Example 2
Input
a
Output
0
Hints
- First precompute isPal[i][j] for all substrings: s[i] == s[j] and (j − i < 2 or isPal[i+1][j−1]).
- cuts[i] = minimum cuts for s[0..i]: 0 if the whole prefix is a palindrome, else min over j of cuts[j−1] + 1 where s[j..i] is a palindrome.
Approach
Fill isPal with i going downward so isPal[i+1][j−1] is ready. Then compute cuts left to right: the last piece of an optimal partition of s[0..i] is some palindrome s[j..i]; if j = 0 no cut is needed, otherwise it costs one cut plus cuts[j−1]. Use a byte/bool table — 2000 × 2000 = 4·10^6 entries.
Complexity: O(n²) time · O(n²) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int n = s.size();
vector<vector<char>> pal(n, vector<char>(n, 0));
for (int i = n - 1; i >= 0; i--)
for (int j = i; j < n; j++) pal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1]);
vector<int> cuts(n, 0);
for (int i = 0; i < n; i++) {
if (pal[0][i]) continue;
cuts[i] = INT_MAX;
for (int j = 1; j <= i; j++)
if (pal[j][i]) cuts[i] = min(cuts[i], cuts[j - 1] + 1);
}
cout << cuts[n - 1] << "\n";
return 0;
}Python solution
s = input().strip()
n = len(s)
# pal_end[i] = list of start indices j such that s[j..i] is a palindrome (expand around centres)
starts = [[] for _ in range(n)]
for c in range(2 * n - 1):
l, r = c // 2, (c + 1) // 2
while l >= 0 and r < n and s[l] == s[r]:
starts[r].append(l)
l -= 1
r += 1
cuts = [0] * n
for i in range(n):
best = n
for j in starts[i]:
best = 0 if j == 0 else min(best, cuts[j - 1] + 1)
if best == 0:
break
cuts[i] = best
print(cuts[-1])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
String s = new Scanner(System.in).next();
int n = s.length();
boolean[][] pal = new boolean[n][n];
for (int i = n - 1; i >= 0; i--)
for (int j = i; j < n; j++) pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
int[] cuts = new int[n];
for (int i = 0; i < n; i++) {
if (pal[0][i]) continue;
cuts[i] = Integer.MAX_VALUE;
for (int j = 1; j <= i; j++)
if (pal[j][i]) cuts[i] = Math.min(cuts[i], cuts[j - 1] + 1);
}
System.out.println(cuts[n - 1]);
}
}Solve Palindrome Partitioning II online · All practice problems