Palindromic Partitioning

Given a string \( s \), your task is to determine the minimum number of cuts required to partition the string such that every substring is a palindrome.

A string is a palindrome if it reads the same backward as forward. Formally, a substring \( s[i \ldots j] \) is a palindrome if:

\( s[i] = s[j] \) for all valid indices and recursively the inner substring is also a palindrome.

For example:

• For \( s = \texttt{aab} \), one optimal partition is \( \texttt{aa} | \texttt{b} \) with exactly one cut.
• For \( s = \texttt{a} \), the string is already a palindrome so no cut is needed (0 cuts).
• For \( s = \texttt{abc} \), the optimal partition is \( \texttt{a} | \texttt{b} | \texttt{c} \) which requires 2 cuts.

This problem requires a dynamic programming approach to check for palindromic substrings and then compute the minimum cuts needed.

inputFormat

The input is provided via standard input (stdin) and consists of a single line containing the string \( s \). The string \( s \) will contain only lowercase English letters.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of cuts required to partition the input string such that every substring is a palindrome.

## sample

aab

1