Palindrome Partitioning Minimum Cut

You are given a string s. Partition the string into substrings so that each substring is a palindrome. Your task is to determine the minimum number of cuts required to partition s in such a way that every substring is a palindrome.

For example, if the string is abccbc, the minimum cuts needed is 2 (one optimal partition is "a|bccb|c").

The problem can be formally defined as follows:

Given a string \(s\) of length \(n\), find the minimum integer \(c\) such that there exists a partition of \(s\) into \(c+1\) substrings, each of which is a palindrome.

inputFormat

The input consists of a single line containing the string s via standard input (stdin). Note that s may be an empty string.

outputFormat

Output a single integer representing the minimum number of cuts needed so that every substring in the partition is a palindrome. The result should be printed to standard output (stdout).

abccbc

2