Garmaine Staff asked 2 years ago

Problem description:

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.

Problem link

Though I was able to code O(N^3) solution but facing problem in O(N^2) optimization

This is the optimized solution explanation

In the very first line "cut[i] is the minimum of cut[j – 1] + 1 (j <= i), if [j, i] is palindrome"

Why is this the case? Formal proof is not essential, intuition will also do.