Subtask 1

We can use dynamic programming to solve this subtask.

Let ~dp_1[l][r][c] =~ whether the substring ~s_l, s_{l+1}, \dots, s_r~ can be merged into the letter ~c~. The transition is pretty simple: we just check if we can merge two 'halves' of the string into our desired letter, with the base case being a substring of length ~1~.

Then, let ~dp_2[i] =~ the minimum number of characters we can merge the prefix ~s_1, s_2, \dots, s_i~ into. In this case, we no longer perform merge operations and instead use our precomputed values of ~dp_1~. Formally, ~dp_2[i] = \min_{1 \le j < i} (dp_2[j]+1\text{ if }dp_1[j+1][i][c]\text{ is true for some }c)~.

The final answer is ~dp_2[|S|]~.

Time complexity: ~\mathcal{O}(|S|^3)~ per test case.

Subtask 2

One thing you may notice after trying the merging process on some strings is that is you can reduce it to ~1~ or ~2~ characters almost every time. In fact, this is a very useful observation:

Let's denote our current string after some number of merges (possibly ~0~) as ~s~. We'll assume that ~|s|>3~ and ~s~ contains at least ~2~ types of characters.

We can show that if these constraints are satisfied, we can always reduce ~s~ by ~1~ character while making sure that it contains at least ~2~ types of characters.

At every step, we just need to merge an index ~i~ ~(1 \le i < |s|)~ such that ~s_i \ne s_{i+1}~ and the frequency of either (or both) ~s_i~ and ~s_{i+1}~ is more than ~1~. We can show that such an index will always exist through the following:

• At least one character (a, b, or c) will have a frequency ~> 1~ by the pigeonhole principle as ~|s| > 3~. We'll denote this character as ~x~.
• As there are at least ~2~ distinct types of characters and ~x~ has positive frequency, there must exist an adjacent pair of characters in ~s~ such that exactly one of the characters is ~x~.

Thus, if our initial string contains at least ~2~ types of characters, we can always reduce it to a string of length ~3~ with at least ~2~ types of characters, which can then be further reduced to a string of size ~2~ (and then possibly further). This means that given the initial string, the only possible answers are ~1~, ~2~, and ~|s|~.

For now, you can just assume that applying this greedy method is always optimal without showing how it distinguishes between cases where the answer is ~1~ and where the answer is ~2~. The proof for this will be in the solution for the final subtask.

To pass this subtask, we can just simulate the merges, which has a time complexity of ~\mathcal{O}(|S|^2)~.

Time complexity: ~\mathcal{O}(|S|^2)~ per test case.

Subtask 3

This solution builds on the proof from the second subtask.

Here's something interesting: every time a merge operation occurs, the frequency of every character changes by ~1~ (the characters merged change by ~-1~, while the new character changes by ~+1~). This means that the parity of the frequency of every character will flip on a merge operation.

Now consider a string of length ~3~ that contains at least ~2~ distinct characters, but will result in an answer of ~2~: the only case where this happens is if every character has frequency ~1~. Furthermore, this is also the only string of length ~3~ where the frequency of every character has the same parity.

Next, recall that a merge operation changes the parity of every frequency, meaning that if the initial string ~S~ has the same parity of frequency for each character, it will still retain this property after the merge (and vice versa). This means that all initial strings ~S~ with the property of the frequency of each character having the same parity can only merge into a string of length ~3~ that will result in an answer of ~2~, and if the frequency of any character has a different parity, this state will never be reached allowing the ~S~ to reduce to length ~1~.

Lastly, as all you need to compute the answer is the frequency of every character, we can solve the problem in linear time.

Time complexity: ~\mathcal{O}(|S|)~ per test case.