Below, let \(s_i\) denote the \(i\)-th character of \(S\), and assume that \(S\) has \(c_a\) occurrences of a and \(c_b\) occurrences of b. First, let us do a case analysis on the last character of \(S\).

If \(S\) ends with a:

Let \(k\) be the minimum integer such that \(s_k=\dots =s_{|S|}=\) a. Also, let \(s_0=\) b for convenience.

By repeating the operation below, we can make \(S\) start with bb...b (\(c_b\) bs), so bb...b is a lower bound of the answer.

• If there exists \(1\leq i < k\) such that \(s_{i-1}=\) b, \(s_i=\) a, \(s_{i+1}=\) a, do the operation on \(s_i\) and \(s_k\).
• Otherwise, if there are multiple indices \(1\leq i < k\) such that \(s_{i-1}=\) b, \(s_i=\) a, \(s_{i+1}=\) b, choose two of them arbitrarily and do the operation between them.
• Otherwise, if there exists \(i<k\) such that \(s_i=\) a, do the operation on \(s_i\) and \(s_k\) and terminate.
• Otherwise, terminate.

The proof of this relies on the facts that the first two operations keep the property that \(S\) ends with a, and that there is at most one index \(i < k\) such that \(s_i=\) a when the first two operations cannot be done.

To achieve the lexicographically maximum result, we need to find the maximum \(t\) such that we can change \(S\) to bb...baa...a (\(c_b\) bs and \(t\) as). Let us prove that the above operation achieves the maximum value of \(t\), that is, minimizes the number of operations. Let us call the consecutive as at the end of \(S\) the tail.

Assume that there are \(x\) substrings of length \(1\) consisting of a and \(y\) substrings of length \(2\) consisting of b other than the tail. That is, there are \(x\) pairs of integers \(1\leq i< j < k\) such that \(s_{i-1}=\) b, \(s_i=\dots =s_j=\) a, \(s_{j+1}=\) b whose “length” \(j-i+1\) is \(1\), and \(y\) such pairs of integers whose length is \(2\). Here we define the potential of \(S\), \(\phi(S)\), as \(x+2y\).

Then, we can see that any operation on two as decreases \(\phi(S)\) by at most \(2\). Since the desired string has the potential of \(0\), we need at least \(\lceil \phi(S)/2 \rceil\) operations. Additionally, we can see that the above operation achieves this minimum number of operation required, from the facts that the first and second actions in the operation decrease \(\phi(S)\) by \(2\), and that the third action is done at most once.

Thus, in this case, we can find the answer from the potential. We can easily find the potential in linear time, so the answer can also be found in linear time.

If \(S\) ends with b:

In this case, it is impossible to make \(S\) ends with a without deleting b. Let us do another case analysis on the parity of \(c_a\) and what the tail looks like.

If \(c_a\) is even:

By repeating the operation on two as, we can change \(S\) to bb...b (\(c_b\) bs), and we cannot bring a to the end of \(S\), so the answer is bb...b (\(c_b\) bs).

If \(c_a\) is odd and \(S\) ends with ab:

By repeating the operation on two as that are not at the end of \(S\), we can change \(S\) to bb...bab (\(c_b-1\) bs, one a, and one b). It is impossible to make a lexicographically greater string by deleting bs, and we cannot bring a to the end without deleting b, so this is the lexicographically greatest string we can make.

If \(c_a\) is odd and \(S\) ends with abb:

By repeating the operation on two as that are not at the end of \(S\), we can change \(S\) to bb...bab (\(c_b-2\) bs, one a, and two bs). It is impossible to make a lexicographically greater string by deleting bs, and we cannot bring a to the last two positions in \(S\) without deleting b, so this is the lexicographically greatest string we can make.

If \(c_a\) is odd and \(S\) ends with bbb:

If \(S\) is aa...abb...b (\(c_a\) as and \(c_b\) bs), we cannot bring b to the beginning, so the lexicographically greatest string we can make is stbb...b (one a and \(c_b\) bs), which can be obtained by repeating the operation on two as.

Otherwise, we can bring a to the end of \(S\) by doing the following operation just once:

• If there exists \(1\leq i \leq |S|-2\) such that \(s_{i}=\) b, \(s_{i+1}=\) a, \(s_{i+2}=\) a, do the operation on \(s_i\) and \(s_{|S|}\) (Operation A).
• Otherwise, choose \(1\leq i \leq |S|-2\) such that \(s_{i}=\) b, \(s_{i+1}=\) a, \(s_{i+2}=\) b and do the operation on \(s_i\) and \(s_{|S|}\) (Operation B).

To the string obtained this way, we can do the operation described above in the case where \(S\) ends with b to make \(S\) begin with bb...b (\(c_b-2\) bs). Since it is impossible to make \(S\) begin with \(c_b-2\) or more consecutive bs without deleting bs, so there will be \(c_b-2\) consecutive bs at the beginning of the answer.

Now, similarly to the previous case, in order to achieve the lexicographically greatest result, we need to find the maximum \(t\) such that we can change \(S\) to bb...baa...a (\(c_b-2\) bs and \(t\) as). Let us prove that the above operation achieves this maximum value of \(t\), that is, minimizes the number of operations. We define the potential of \(S\), \(\phi(S)\), in the same way as in the previous case.

In order to bring a to the end of \(S\), we need to do the operation on the b at the end of \(S\). This operation decreases \(\phi(S)\) by at most \(2\). To keep \(c_b-2\) bs, we can do at most one operation on bs, so any operation, including the ones on as, decreases \(\phi(S)\) by at most \(2\), and we need \(\lceil \phi(S)/2 \rceil\) operations.

If there exists \(1\leq i \leq |S|-2\) such that \(s_{i}=\) b, \(s_{i+1}=\) a, \(s_{i+2}=\) a, Operation A decreases \(\phi(S)\) by \(2\), so we can make the lexicographically greatest string by the method above.

Below, we assume there is no such \(i\). Then, Operation B decreases \(\phi(S)\) by \(1\). Thus, if the \(\phi(S)\) is initially odd, we can make the lexicographically greatest string by the method above.

If the \(\phi(S)\) is initially odd, the method above does \(\phi(S)/2+1\) operations. That is, we have to show that it is impossible to change \(S\) to bb...baa...a (\(c_b-2\) bs and \(t\) as) in \(\phi(S)/2\) operations. Note that, in such a sequence of operations, every operation must decrease \(\phi(S)\) by \(2\).

In \(S\), the operations that we can do on as are as follows. Here, we call the consecutive as at the beginning of \(S\) the head.

• Do the operation on two as in the head, which decreases \(\phi(S)\) by at most \(1\).
• Do the operation on an a in the head and an a not in the head. \(\phi(S)\) will decrease by \(2\) only when the head has two or fewer as, but this will not make new \(1 \leq i\) such that \(s_{i}=\) b, \(s_{i+1}=\) a, \(s_{i+2}=\) a.
• Do the operation on two as not in the head. This will not make new \(1 \leq i\) such that \(s_{i}=\) b, \(s_{i+1}=\) a, \(s_{i+2}=\) a.

Thus, after all, we can see that it is impossible to decrease \(\phi(S)\) by \(2\) when doing the operation on bs, so we need \(\phi(S)/2+1\) operations. From this fact, we can restore the value \(t\). Since we can find the value \(\phi(S)\) in linear time, we have solved the problem in linear time using all the arguments above.