RemovevomeR

Key observation

A binary string is only truly stuck in two cases:

• length $1$;
• length $2$ with two different characters, i.e. 01 or 10.

Why? Look at any binary substring of length $3$.

If it has equal adjacent characters, then those two characters form a palindrome of length $2$.

If it does not have equal adjacent characters, then it must be either 010 or 101, which is a palindrome of length $3$.

So every binary string of length at least $3$ contains some palindromic substring of length at least $2$. Translation: as long as the string has length at least $3$, you are allowed to delete something. The string is not safe. It is very much on the chopping block.

So the answer is only $1$ or $2$

We can never reach length $0$, because an operation needs a palindrome of length at least $2$, and once the string has length $1$, no operation is possible.

So the best possible answer is $1$. If we cannot get to $1$, the answer must be $2$.

A length-$2$ string can be reduced to length $1$ exactly when its two characters are equal:

• 00 is a palindrome, delete one 0;
• 11 is a palindrome, delete one 1;
• 01 and 10 are not palindromes, so they are stuck.

Therefore, the whole problem becomes:

Can we make the final length-$2$ string have two equal characters?

When is answer $1$ possible?

Deleting characters never changes the relative order of the characters that remain. So if the original string contains two equal characters somewhere, we can keep those two characters as survivors.

For example, if the string has two 0s, we can aim to leave exactly those two 0s. Same for two 1s.

Now we need to justify that the extra characters can actually be removed. While the current length is at least $3$, we already proved there is always some valid palindromic substring available, so we can keep deleting characters until only our chosen equal pair remains. Since that pair is 00 or 11, it is itself a palindrome, and one more deletion gives length $1$.

So:

$$\text{answer} = 1 \quad \text{if some character appears at least twice.}$$

When is answer $2$ forced?

If no character appears twice, then because the alphabet is binary, the string has length at most $2$.

• If $n = 1$, answer is $1$.
• If $n = 2$, the two characters must be different, so the string is 01 or 10, and no operation is possible. Answer is $2$.

This also kills a common false assumption: you do not need dynamic programming, graph search, or some cursed substring simulation. The operation sounds flexible because it is flexible; the binary alphabet makes the final structure tiny.

Algorithm

For each test case:

1. Count zeros and ones.
2. If $n = 1$, print $1$.
3. Else if either count is at least $2$, print $1$.
4. Otherwise print $2$.

Equivalently, print $1$ unless the string has length $2$ and its two characters are different.

Correctness proof

We prove the algorithm prints the minimum possible final length.

First, any binary string of length at least $3$ has a valid operation. Consider any three consecutive characters. If two adjacent characters are equal, those two form a palindromic substring of length $2$. Otherwise, the three characters must alternate, so they are either 010 or 101, a palindromic substring of length $3$. Thus no string of length at least $3$ is final.

Second, the only final strings have length $1$, or length $2$ with different characters. A length-$1$ string has no substring of length at least $2$. A length-$2$ string is reducible exactly when both characters are equal. By the previous paragraph, longer strings are always reducible.

Third, if some character appears at least twice in the original string, length $1$ is achievable. Choose two equal occurrences and keep them as the intended final pair. While the string has length at least $3$, there is always at least one valid operation, so characters can be deleted until only two characters remain; choose deletions so the two equal chosen occurrences survive. The remaining pair is 00 or 11, hence a palindrome, so one more operation reduces the string to length $1$.

Fourth, if no character appears twice, then since the alphabet is binary, $n \le 2$. If $n=1$, the minimum is clearly $1$. If $n=2$, the two characters differ, so the string has no palindromic substring of length at least $2$ and the minimum is $2$.

Therefore the algorithm always outputs exactly the minimum possible final length.

Complexity

Each test case is processed in $O(n)$ time and $O(1)$ memory. With $n \le 100$, this is basically free; the CPU will not even have time to feel important.