Minimum Palindrome Partitions

Given a string s, compute the minimum number k such that the string can be partitioned into k non-empty substrings, each of which is a palindrome. A palindrome is defined as a string that reads the same forwards and backwards. The problem can be solved using dynamic programming with the recurrence:

\( dp[i] = \min_{0 \leq j < i} \{ dp[j] + 1 \} \),

where the state \(dp[i]\) represents the minimum number of partitions for the substring s[0 \ldots i-1], and the transition considers a valid palindrome substring s[j...i-1].

Your task is to compute and output this minimum number for a given input string.

inputFormat

The input consists of a single line containing the string s.

It is guaranteed that s contains only lowercase English letters.

outputFormat

Output an integer, which is the minimum number of palindromic substrings into which s can be partitioned.

abac

2