Longest Palindromic Substring Length

Given a string s consisting of uppercase and lowercase English letters, determine the length of the longest substring of s that is a palindrome.

A palindrome is a sequence of characters that reads the same backward as forward. For example, the string "racecar" is a palindrome because reversing it produces "racecar". Your task is to find the length of the longest palindromic substring in the input string.

Note: Consider that a single character is also a palindrome of length 1. If the input string is empty, the answer is 0.

Examples:

• Input: "babad" → Output: 3 (palindrome could be "bab" or "aba")
• Input: "cbbd" → Output: 2 (palindrome is "bb")
• Input: "racecar" → Output: 7

The solution must use the traditional dynamic programming approach to solve the problem. Also, if you use any mathematical formulas, represent them using LaTeX format. For example, the recurrence relation can be expressed as: $$ table[i][j] = \begin{cases} \text{true} & \text{if } s[i] = s[j] \text{ and } table[i+1][j-1] \text{ is true} \\ \text{false} & \text{otherwise.} \end{cases} $$

inputFormat

The input consists of a single line containing the string s. Read the input from standard input (stdin).

Constraints:

• The string s contains only uppercase and lowercase English letters.
• The length of s is between 0 and 10,000.

outputFormat

Output a single integer representing the length of the longest palindromic substring. Write your output to standard output (stdout).

## sample

babad

3