Palindrome Partitioning II

Given a nonempty lowercase-English string s, partition the whole string into contiguous, nonempty palindromic substrings. Return the minimum number of cuts…

Given a nonempty lowercase-English string s, partition the whole string into contiguous, nonempty palindromic substrings. Return the minimum number of cuts between pieces. Each original character belongs to exactly one piece, in order. A palindrome reads identically backward and forward. Do not return the pieces. Cuts and pieces differ: a partition with p pieces has p−1 cuts. If the whole string is a palindrome, the answer is 0. Every input has a valid partition because every single character is a palindrome.

- 1 <= s.length <= 2000. - s contains only lowercase English letters a through z. - The visualizer accepts 1..8 letters; longer valid inputs are coding-only.

Example 1: input s = "aab"; output 1. The partition aa | b uses one cut; aab itself is not a palindrome.

Example 2: input s = "abaaba"; output 0. The whole string is a palindrome and needs no cut.

Example 3: input s = "aaba"; output 1. The partition a | aba uses one cut. Greedily choosing the longest palindromic prefix aa leaves b | a and uses two cuts.

Category: Strings. Topic: dynamic-programming. Difficulty: hard. Patterns: dynamic-programming.