273. Palindrome Partitioning II (Minimum Cuts)

Given a string s, partition it so that every substring of the partition is a palindrome. Return the minimum number of cuts needed.

Input: A quoted string s.

Output: Integer — minimum cuts.

Examples

Example 1

Input: "aab"
Output: 1
Explanation: ['aa','b'] needs one cut.

Example 2

Input: "a"
Output: 0
Explanation: Already a palindrome.

Example 3

Input: "abc"
Output: 2
Explanation: ['a','b','c'].