Palindrome Partitioning Minimum Cuts

Problem Statement

Given a string text, split text such that every part of the split is a palindrome.

Return the smallest number of cuts needed to divide text into palindromic substrings.

Examples

Example 1:
Input: "abbc"
Output: 1
Explanation: One way to split is ["abb", "c"], but "abb" is not a palindrome.
A better split is ["a", "bb", "c"], which requires 2 cuts.
However, the minimum cuts required is 1, splitting as ["abba", "c"], but since "abba" is not substring here, the best palindrome partitions are ["a","bb","c"] with 2 cuts. So output should be 2.

Example 2:
Input: "racecar"
Output: 0
Explanation: The entire string "racecar" is a palindrome, so no cuts are needed.

Example 3:
Input: "noonabba"
Output: 1
Explanation: Splitting into ["noon", "abba"] requires 1 cut, and both parts are palindromes.

Constraints

• 1 ≤ length of text ≤ 1800
• text consists only of lowercase English letters.