Palindrome Partitioning II

Hard

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

Example 1

Input:  s = "aab"
Output: 1

Example 2

Input:  s = "a"
Output: 0

Example 3

Input:  s = "ab"
Output: 1

Constraints

• 1 <= s.length <= 2000
• s consists of lowercase English letters.