# Palindromic Partitioning

Let's solve the Palindromic Partitioning problem using Dynamic Programming.

## 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

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.