234. Palindrome Partitioning II — Minimum Cuts

Hard · Dynamic Programming

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

Examples

Example 1
Input: s = "aab"
Output: 1
Explanation: "aab" → ["aa","b"] — one cut
Example 2
Input: s = "a"
Output: 0
Explanation: Already a palindrome

Constraints