Palindromic Partitioning

Statement

Suppose you are given a string, s. You need to perform the minimum number of cuts to divide the string into substrings, such that all the resulting substrings are palindromes.

Let’s say you have the following string:

• “apple”

The resulting substrings after performing the minimum number of cuts are:

• “a”$|$“pp”$|$“l”$|$“e”

So, a minimum of $3$ cuts are required.

Constraints:

• $1 \leq$ s.length $\leq 1.5\times10^3$
• s consists of only lowercase English characters.

Examples