Tear It Apart
Contest: Educational Codeforces Round 147 (Rated for Div. 2)
Difficulty rating: 1300
Tags: brute force, implementation, math, strings

You are given a string $$$s$$$, consisting of lowercase Latin letters.

In one operation, you can select several (one or more) positions in it such that no two selected positions are adjacent to each other. Then you remove the letters on the selected positions from the string. The resulting parts are concatenated without changing their order.

What is the smallest number of operations required to make all the letters in $$$s$$$ the same?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The only line of each testcase contains a string $$$s$$$, consisting of lowercase Latin letters. Its length is from $$$1$$$ to $$$2 \cdot 10^5$$$.

The total length of the strings over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each testcase, print a single integer — the smallest number of operations required to make all the letters in the given string $$$s$$$ the same.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase, you can select positions $$$2, 4$$$ and $$$6$$$ and remove the corresponding letters 'b', 'c' and 'b'.

In the third testcase, the letters in the string are already the same, so you don't have to make any operations.

In the fourth testcase, one of the possible solutions in $$$2$$$ operations is the following. You can select positions $$$1, 4, 6$$$ first. The string becomes "bce". Then select positions $$$1$$$ and $$$3$$$. The string becomes "c". All letters in it are the same, since it's just one letter.

Example input:
5
abacaba
codeforces
oooooooo
abcdef
mewheniseearulhiiarul

Example output:
1
3
0
2
4

Editorial:
The resulting string looks like a single letter repeated a number of times. That sounds too vague. Let's fix the exact letter $$$c$$$ that will be left. Since the size of the alphabet is only $$$26$$$, we can afford that.
The letters now separate into letters $$$c$$$ and other letters. And all other letters can be treated as indistinguishable from each other. Let's make letter $$$c$$$ into a binary $$$1$$$ and any other letter into a binary $$$0$$$. Our goal is to remove all zeros from the string with the given operations.
First, notice that it doesn't help you to removes ones. If some operation contains both ones and zeros, then taking ones out of it doesn't make any zeros in it adjacent. At the same time, these ones can only help you separate adjacent zeros later.
Thus, we have some blocks of zeros, separated by the blocks of ones. We want to remove only zeros. Notice how these blocks can be solved completely independently of each other. If you solve block $$$1$$$ in $$$\mathit{cnt}_1$$$ operations, block $$$2$$$ in $$$\mathit{cnt}_2$$$ operations, ..., block $$$k$$$ in $$$\mathit{cnt}_k$$$ operations, then you can solve the entire string in $$$\max(\mathit{cnt}_1, \mathit{cnt}_2, \dots, \mathit{cnt}_k)$$$ operations. Since the blocks are separated by the blocks of ones, you can combine the first operations for all blocks into one big operation and so on.
The only thing left is to calculate the number of operations for a single block. Let it have length $$$l$$$. Basically, in one operation, you can decrease its length to $$$\lfloor \frac l 2 \rfloor$$$. You can see that the longer the block, the greater answer it has. So you can find the longest block first, then calculate the answer for it. You can either use this iterative formula or notice that it's a logarithm of $$$l$$$ in base $$$2$$$ and calculate that however you want.
To find the lengths of the blocks of zeros, you can use two pointers.
Overall complexity: $$$O(|\mathit{AL}| \cdot n)$$$ per testcase.
This problem can also be solved in $$$O(n \log n)$$$ on an arbitrarily large alphabet. Basically, when you fix a letter, you can tell the lengths of the blocks of other letters by looking at the occurrences of the letter. For occurrences $$$i_1, i_2, \dots, i_k$$$, the lengths of the blocks are $$$i_1 - 1, i_2 - i_1, \dots, i_k - i_{k-1}, n - i_{k}$$$. So we can calculate the answer for a letter in $$$O(\mathit{number\ of\ its\ occurrences})$$$. The total of that for all letters is $$$O(n)$$$.