Dreamoon Likes Strings
Contest: Codeforces Round 631 (Div. 1) - Thanks, Denis aramis Shitov!
Difficulty rating: 3100
Tags: constructive algorithms, data structures

Dreamoon likes strings. Today he created a game about strings:

String $$$s_1, s_2, \ldots, s_n$$$ is beautiful if and only if for each $$$1 \le i < n, s_i \ne s_{i+1}$$$.

Initially, Dreamoon has a string $$$a$$$. In each step Dreamoon can choose a beautiful substring of $$$a$$$ and remove it. Then he should concatenate the remaining characters (in the same order).

Dreamoon wants to use the smallest number of steps to make $$$a$$$ empty. Please help Dreamoon, and print any sequence of the smallest number of steps to make $$$a$$$ empty.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 200\,000$$$), denoting the number of test cases in the input.

For each test case, there's one line with a non-empty string of lowercase Latin letters $$$a$$$.

The total sum of lengths of strings in all test cases is at most $$$200\,000$$$.

Output format:
For each test case, in the first line, you should print $$$m$$$: the smallest number of steps to make $$$a$$$ empty. Each of the following $$$m$$$ lines should contain two integers $$$l_i, r_i$$$ ($$$1 \leq l_i \leq r_i \leq |a|$$$), denoting, that the $$$i$$$-th step is removing the characters from index $$$l_i$$$ to $$$r_i$$$ in the current string. (indices are numbered starting from $$$1$$$).

Note that after the deletion of the substring, indices of remaining characters may change, and $$$r_i$$$ should be at most the current length of $$$a$$$.

If there are several possible solutions, you can print any.

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

Example input:
4
aabbcc
aaabbb
aaa
abacad

Example output:
3
3 3
2 4
1 2
3
3 4
2 3
1 2
3
1 1
1 1
1 1
1
1 6

Editorial:
Denoting a string of length two which contains two $$$i$$$-th letter as $$$t_i$$$. For example, $$$t_0$$$ is "aa", $$$t_1$$$ is "bb" .
And let $$$c_i$$$ be the occurrence count of $$$t_i$$$ as a substring in $$$a$$$. For example, when $$$a =$$$ "aaabbcaa", $$$c_0 = 3, c_1 = 1$$$, and for other $$$i$$$, $$$c_i = 0$$$.
In this problem, if only asking contestants output the smallest number of steps to make $$$a$$$ empty, the answer is simple. You just need to output $$$\max(\left \lceil\frac{\sum c_i}{2} \right\rceil,\max_{0 \le i \le 25}\limits{c_i})+1$$$. (I will call this fomula for a given string $$$a$$$ as $$$f(a)$$$ behind.)
Firstly, let's see how the value of all $$$c_i$$$ change in one step. There are only four kinds of possible change for all $$$c_i$$$.
1. For some $$$i$$$, $$$c_i$$$ is decreased by one. For example, deleting the first two letters of "abb".
2. For two different values $$$i$$$ and $$$j$$$. $$$c_i$$$ and $$$c_j$$$ are both decrease by one. For example, deleting the second and third letter of "aabb".
3. Nothing changes for all $$$c_i$$$. For example, deleting the first letter from "abb".
4. For some $$$i$$$, $$$c_i$$$ is added by one. For example, deleting the second letter from "aba".
Now, Let's consider how will these changes affect the $$$f(a)$$$. Amazing! All possible changes will decrease the value of $$$f(a)$$$ at most one! So if we can construct an algorithm to achieve it, then we solve it.
Now I introduce an algorithm of which time complexity is $$$O(n)$$$.
The algorithm can be divided into three phases.
1.
In this phase, we maintain a stack that stores the position of substring $$$t_i$$$ in the current string from left to right. When we iterate to a string $$$t_i$$$, there are two cases. Assum the top element in the stack is $$$t_j$$$. When $$$i$$$ is equal to $$$j$$$, we just add t_i into the stack. But if $$$i \ne j$$$, we do a step that removing all letters from the second letter of $$$t_j$$$ to the first letter of $$$t_i$$$. and pop $$$t_j$$$ from the stack. If there is any moment that $$$\left \lceil\frac{\sum c_i}{2} \right\rceil \le \max_{0 \le i \le 25}\limits{c_i})+1$$$ is hold (So maybe you won't do anything in this phase), the phase will be terminated.
2.
In this phase, there must be an unique $$$x$$$ satisifying $$$c_x \ge \left \lceil\frac{\sum c_i}{2} \right\rceil$$$.
we also maintain a stack that stores the position of substring $$$t_i$$$ in the current string from left to right. But when we iterate to a string $$$t_i$$$, the action we should do are different from the first phase.
Assum the top element in the stack is $$$t_j$$$. When there is exactly one number among $$$i$$$ and $$$j$$$ is $$$x$$$, we do a step that removing all letters from the second letter of $$$t_j$$$ to the first letter of $$$t_i$$$. and pop $$$t_j$$$ from the stack. Otherwise, we just add $$$t_i$$$ into the stack.
3.
When the algorithm enters the phase, for all $$$i$$$ except $$$x$$$, $$$c_i$$$ will be $$$0$$$. So we can use all occurrence of $$$t_x$$$ to divide the string into $$$c_x+1$$$ segment and remove each segment one by on. After that the string will become empty.
Please see the reference code for the implementation detail.