Minimum Palindrome Partitioning Cuts

Given a string s, partition it into substrings such that every substring is a palindrome. Your task is to determine the minimum number of cuts required to achieve this partitioning.

A palindrome is a string that reads the same backward as forward. For example, "racecar" and "aba" are palindromes, while "abc" is not.

The answer is defined as the minimum number of cuts needed to divide the string into palindromic substrings.

For instance, for s = "abac", one optimal partition is "aba" | "c", so the answer is 1. Similarly, for s = "aab", one optimal partition is "aa" | "b", and the answer is also 1.

Note: If the entire string is a palindrome, no cuts are needed so the answer is 0.

Mathematically, if we let dp[i] represent the minimum number of cuts needed for the substring s[0 \, \ldots\, i], the recurrence can be written in \( \LaTeX \) as follows:

\[ dp[i] = \begin{cases} 0, & \text{if } s[0\ldots i] \text{ is a palindrome} \ \min_{0 \leq j < i} \{ dp[j] + 1 \} \quad \text{for which } s[j+1\ldots i] \text{ is a palindrome}, & \text{otherwise} \end{cases} \]

inputFormat

The input consists of a single line containing the string s.

Constraints: The string s will contain only lowercase English letters.

outputFormat

Output a single integer which is the minimum number of cuts required to partition the string such that every substring is a palindrome.

## sample

abac

1