Minimum Palindromic Deletions to Empty a String

Given a string s, you are allowed to perform the following operation: delete any non-empty substring of s that is a palindrome. Your task is to determine the minimum number of operations required to delete the entire string s.

A palindrome is a string that reads the same forward and backward, i.e., a string \( s \) is a palindrome if \( s = s^R \), where \( s^R \) denotes the reverse of s.

inputFormat

The input consists of a single line which contains the string s (1 ≤ |s| ≤ 1000), where |s| denotes the length of the string.

outputFormat

Output a single integer — the minimum number of operations required to delete the entire string s.

ababa

1