Palindrome partitioning — minimum cuts

Hard

Problem

Return the minimum number of cuts needed to split the string into pieces that are all palindromes.

Example 1

Input:  "aab"
Output: 1

"aa" | "b".

Example 2

Input:  "ababbbabbababa"
Output: 3

Also asked as: Palindrome PartitioningProblem

Test cases

Case 1

Input:    "aab"
Expected: 1

Case 2

Input:    "ababbbabbababa"
Expected: 3

Case 3

Input:    "abc"
Expected: 2

Case 4

Input:    "aba"
Expected: 0

Case 5

Input:    "a"
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Precompute isPalindrome, then 1-D cut DP

Time O(n²)Space O(n²)

pal[i][j] via interval DP. cuts[i] = min cuts for s[0..i]; if s[j..i] is a palindrome, cuts[i] = min(cuts[i], cuts[j−1] + 1), with cuts[−1] = −1.

function minCut(s) {
const n = s.length;
const pal = Array.from({ length: n }, () => new Array(n).fill(false));
for (let i = n - 1; i >= 0; i--)
for (let j = i; j < n; j++)
pal[i][j] = s[i] === s[j] && (j - i < 2 || pal[i + 1][j - 1]);
const cuts = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
if (pal[0][i]) { cuts[i] = 0; continue; }
cuts[i] = i;
for (let j = 1; j <= i; j++)
if (pal[j][i]) cuts[i] = Math.min(cuts[i], cuts[j - 1] + 1);
}
return cuts[n - 1];
}