Palindrome Partitioning II - Hard DSA Problem | Thita.ai
Palindrome Partitioning II
Difficulty: Hard
Category: DSA
Topics: Dynamic Programming
Asked at: Amazon, Google
Given a string `s`, partition `s` such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of `s`.
Example 1:
Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
Example 2:
Input: s = "a"
Output: 0
Example 3:
Input: s = "ab"
Output: 1
Constraints:
`1 <= s.length <= 2000`
`s` consists of lower-case English letters only.