Minimum Palindrome Partitioning

You are given a string s and are required to split it into the smallest number of contiguous substrings such that each substring is a palindrome.

A palindrome is a sequence of characters that reads the same forwards and backwards. The task is to compute the minimum number of palindromic substrings into which the given string can be partitioned.

Note: The answer is the number of substrings in the optimal partition. For example, for the input "aab", the optimal partition is "aa" and "b", so the answer is 2.

The solution can be derived using dynamic programming. For a given string \( s \) of length \( n \), define \( dp[i] \) as the minimum number of palindromic partitions needed for the substring \( s[i \ldots n-1] \). The recurrence is established by checking every possible substring \( s[i\ldots j] \) that is a palindrome and using the optimal solution for the remainder of the string.

The formula in \( \LaTeX \) is as follows:

\[ \text{dp}[i] = \min_{i \leq j < n} \{1 + \text{dp}[j+1]\}\quad \text{if } s[i\ldots j] \text{ is a palindrome}. \]

The answer for the entire string will then be \( dp[0] \).

inputFormat

The input consists of a single line containing a non-empty string s.

You can assume that the string consists of lowercase English letters.

outputFormat

Output a single integer representing the minimum number of palindromic substrings into which the string can be partitioned.

## sample

aab

2