Let

• $n$ equal the current length of the string
• $\mathrm{maxf}_1$ equal the current largest frequency of any character
• $\mathrm{maxf}_2$ equal the current second largest frequency of any character.

First, notice that we can do some operation exactly when $\mathrm{maxf}_1 < n$.

Case 1: $n\equiv0\pmod{2}$

Claim: If $\mathrm{maxf}_1 \le n/2$ and $n > 0$, we can do an operation such that after the operation, $\mathrm{maxf}_1 \le n/2$.

Proof:

• If $\mathrm{maxf}_1 < n/2$, we can do any operation. After the operation $n_{\mathrm{new}} = n-2$ and $n_{\mathrm{new}}/2 = (n-2)/2 = n/2-1$ and because $\mathrm{maxf}_1 < n/2$, then $\mathrm{maxf}_1 \le n/2-1 = n_{\mathrm{new}}/2$.
• If $\mathrm{maxf}_1 = n/2$ and $\mathrm{maxf}_2 < n/2$, we can do one operation which decreases $\mathrm{maxf}_1$ by one. Now $\mathrm{maxf}_{1\mathrm{new}} = \mathrm{maxf}_1-1 = n/2-1 = n_{\mathrm{new}}/2$, meaning that $\mathrm{maxf}_{1\mathrm{new}} \le n_{\mathrm{new}}/2$. Similar to the previous case, $\mathrm{maxf}_2 \le n/2-1 = n_{\mathrm{new}}/2$.
• If $\mathrm{maxf}_1 = n/2$ and $\mathrm{maxf}_2 = n/2$, we have $\mathrm{maxf}_1 + \mathrm{maxf}_2 = n$. This means that there are no other characters than those two, so we can delete one of each. Now $\mathrm{maxf}_{1\mathrm{new}} = \mathrm{maxf}_1-1 = \mathrm{maxf}_{2\mathrm{new}} = \mathrm{maxf}_2-1 = n/2-1 = n_{\mathrm{new}}/2$, meaning that $\mathrm{maxf}_{1\mathrm{new}} = \mathrm{maxf}_{2\mathrm{new}} \le n_{\mathrm{new}}/2$.

This means that if we have $\mathrm{maxf}_1 \le n/2$ and $\mathrm{maxf}_1 < n$, we can do an operation and keep the first condition satisfied. Thus, we can do operations while $n/2 < n\ \Leftrightarrow\ 0 < n/2\ \Leftrightarrow\ n > 0$. Thus we can always reach the state with $n = 0$. $\square$

Case 2: $n\equiv1\pmod{2}$

Claim: If $\mathrm{maxf}_1 \le \lceil n/2\rceil$ and $n > 1$, we can do an operation such that after the operation, $\mathrm{maxf}_1 \le \lceil n/2\rceil$.

Proof:

• If $\mathrm{maxf}_1 < \lceil n/2\rceil$, we can do any operation. After the operation $n_{\mathrm{new}} = n-2$ and $\lceil n_{\mathrm{new}}/2\rceil = (n_{\mathrm{new}}+1)/2 = (n-2+1)/2 = (n+1)/2 - 1 = \lceil n/2\rceil-1$ and because $\mathrm{maxf}_1 < \lceil n/2\rceil$, then $\mathrm{maxf}_1 \le \lceil n/2\rceil-1 = \lceil n_{\mathrm{new}}/2\rceil$.
• If $\mathrm{maxf}_1 = \lceil n/2\rceil$ and $\mathrm{maxf}_2 < \lceil n/2\rceil$, we can do one operation which decreases $\mathrm{maxf}_1$ by one. Now $\mathrm{maxf}_{1\mathrm{new}} = \mathrm{maxf}_1-1 = \lceil n/2\rceil-1 = \lceil n_{\mathrm{new}}/2\rceil$, meaning that $\mathrm{maxf}_{1\mathrm{new}} \le \lceil n_{\mathrm{new}}/2\rceil$. Similar to the previous case, $\mathrm{maxf}_2 \le \lceil n/2\rceil-1 = \lceil n_{\mathrm{new}}/2\rceil$.
• Notice that the case with $\mathrm{maxf}_1 = \lceil n/2\rceil$ and $\mathrm{maxf}_2 = \lceil n/2\rceil$ doesn't exist as $\mathrm{maxf}_1 + \mathrm{maxf}_2 = 2\lceil n/2\rceil = 2(n+1)/2 = n+1 > n$, which is not possible.

This means that if we have $\mathrm{maxf}_1 \le \lceil n/2\rceil$ and $\mathrm{maxf}_1 < n$, we can do an operation and keep the first condition satisfied. Thus, we can do operations while $\lceil n/2\rceil < n\ \Leftrightarrow\ (n+1)/2 < n\ \Leftrightarrow\ n+1 < 2n\ \Leftrightarrow\ 1 < 2n-n\ \Leftrightarrow\ n > 1$. Thus we can always reach the state with $n = 1$. $\square$