Array String Dynamic Programming Memoization Tabulation
Guru Level

Implement the palindromePartitionMinCuts method that returns the minimum cuts needed to split text into palindrome parts.

The input contains a string text. Your task is to split the string into substrings so that every substring is a palindrome, and return the minimum number of cuts needed.

A palindrome substring reads the same from left to right and right to left.

For example, aab can be split as aa|b. Both parts are palindromes, so only 1 cut is required.

Example 1
Input:
text (string) = aab
Return:
(int) 1
Example 2
Input:
text (string) = a
Return:
(int) 0
Example 3
Input:
text (string) = ab
Return:
(int) 1

First identify which substrings are palindromes, then use dynamic programming to calculate the minimum cuts.

Create a palindrome table where pal[start][end] is true when the substring from start to end is a palindrome. This avoids checking the same substring again and again.

Then calculate cuts[end], the minimum cuts needed for the prefix ending at end. If the whole prefix is already a palindrome, the cut count is 0. Otherwise, try every valid previous palindrome part and keep the minimum.

Pseudocode:

function palindromePartitionMinCuts(text):
    n = length of text
    create palindrome table pal[n][n] with false values
    for end from 0 to n - 1:
        for start from 0 to end:
            if text[start] == text[end] and (end - start < 2 or pal[start + 1][end - 1]):
                pal[start][end] = true
    create cuts array of size n
    for end from 0 to n - 1:
        if pal[0][end] == true:
            cuts[end] = 0
        else:
            cuts[end] = end
            for start from 1 to end:
                if pal[start][end] == true:
                    cuts[end] = minimum(cuts[end], cuts[start - 1] + 1)
    return cuts[n - 1]
Run your code to see the result.