Minimum Palindrome Partition

You are given a string s consisting of lowercase English alphabets. Your task is to determine the minimal number of contiguous substrings into which you can partition the string such that each substring is a palindrome.

A palindrome is a string that reads the same backwards as forwards. For example, "aba" and "racecar" are palindromes, while "abc" is not.

Note: It can be proven that for any non-palindromic string, the answer will always be 2.

Examples:

• If s = "a", then the answer is 1 because "a" is a palindrome.
• If s = "aba", then the answer is 1 because the entire string is a palindrome.
• If s = "abc", then the answer is 2 because it is not a palindrome.

inputFormat

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

outputFormat

Output a single integer representing the minimal number of contiguous substrings required such that each substring is a palindrome.

a

1