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.
30:00
Java
Palindrome Partitioning II
hard
Topics
Companies
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
Constraints:
1≤s.length≤2000
s consists of lowercase English letters only.
Input
arr ={"s":"aab"}
Initialize dp[i] = i (worst case: cut before each char)