Shortest Substring Removal for Palindrome

You are given a string \(S\). Your task is to remove a contiguous substring from \(S\) such that the concatenation of the remaining parts forms a palindrome. A string is a palindrome if it reads the same from left to right and right to left. In other words, find the minimum length \(L\) of a contiguous substring which, when removed from \(S\), leaves a palindrome.

Formally, let \(S[0\ldots n-1]\) be the given string. You need to choose two indices \(i\) and \(j\) (with \(0 \leq i \leq j < n\)) and remove the substring \(S[i\ldots j]\). Let \(T = S[0\ldots i-1] + S[j+1\ldots n-1]\) be the resulting string. The goal is to minimize \(j - i + 1\) such that \(T\) is a palindrome. If \(S\) is already a palindrome, no removal is necessary (i.e. \(L = 0\)).

For example, when \(S = \texttt{abac}\), the shortest removal is of length 1 (removing the last character \(c\) produces \(aba\), which is a palindrome). When \(S = \texttt{aaa}\), the string is already a palindrome, so the answer is 0.

Note: It is guaranteed that an answer always exists (in the worst case, the entire string can be removed).

inputFormat

The input consists of a single line containing the string \(S\). \(S\) is non-empty and consists of lowercase English letters.

outputFormat

Output a single integer representing the minimum length of the contiguous substring that needs to be removed so that the remaining string is a palindrome.

## sample

abac

1

</p>