Palindrome Partitioning Minimum Cuts

Problem

Return the minimum number of cuts needed so that every resulting substring of s is a palindrome.

Precompute which substrings are palindromes in O(n squared), then let dp[i] be the minimum cuts for the prefix ending at i, using 0 when the whole prefix is a palindrome. An empty string needs 0 cuts.

Hint

A palindrome prefix costs zero cuts; otherwise try every palindromic suffix of the current prefix.

Test cases

case 1

in: ["aab"]

expected: 1

case 2

in: ["a"]

expected: 0

case 3

in: ["ab"]

expected: 1

case 4

in: ["ababbbabbababa"]

expected: 3

case 5

in: ["abcba"]

expected: 0

Starter codePython

def min_cut_palindrome_partition(s):
    # Your code here
    pass

5 test cases · run your code against them in the editor