Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. First precompute isPal[i][j] for all substrings: s[i] == s[j] and (j − i < 2 or isPal[i+1][j−1]).
  2. 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