Minimum Palindrome Segments

You are given a string s consisting of lowercase English letters. Your task is to partition the string into the minimum number of segments such that each segment is a palindrome.

A palindrome is a string that reads the same backward as forward. For instance, "racecar" is a palindrome while "abc" is not.

The problem requires you to compute the minimum number of segments into which the string can be split where every segment is a palindrome. You may use dynamic programming to solve this problem efficiently. The key idea is to iterate over all possible partitions and identify if a segment is a palindrome using a helper routine. In formula terms, if we define dp[i] as the minimum segments for the prefix of length i, then:

\(dp[i] = \min_{0 \leq j < i}\{ dp[j] + 1 \}\) provided that the substring \(s[j:i]\) is a palindrome.

The output should be the computed number of segments.

inputFormat

The input is a single string s provided via standard input (stdin). The string consists of lowercase English letters with no spaces.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of palindrome segments into which the input string can be partitioned.

ababa

1