1192. Palindrome Partitioning II — Min Cuts

Given a string s, partition it so that every part is a palindrome. Return the minimum number of cuts needed. The input is JSON {s}.

Input: JSON {s}.

Output: Integer — the minimum cuts.

Examples

Example 1

Input: {"s":"aab"}
Output: 1
Explanation: 'aa' | 'b'.

Example 2

Input: {"s":"a"}
Output: 0
Explanation: Already a palindrome.

Example 3

Input: {"s":"ab"}
Output: 1
Explanation: 'a' | 'b'.