Fewest Palindromic Pieces

You are given a string s consisting of lowercase English letters.

Split s into as few contiguous, non-empty pieces as possible so that every piece is a palindrome and the pieces concatenate back to s in order. A single character is always a palindrome, so this is always possible, and the answer is at most the length of s. Return the number of pieces. The answer for an empty string is 0.

Examples

Example 1

Input: s = "aab"
Output: 2
Explanation: Split into "aa" and "b", both palindromes.

Example 2

Input: s = "abc"
Output: 3
Explanation: No two adjacent characters ever match, so each character must be its own piece.

Example 3

Input: s = "racecar"
Output: 1
Explanation: The whole string is already a palindrome.