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 \lt n$$$.

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

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

Proof:

• If $$$\mathrm{maxf}_1 \lt 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 \lt n/2$$$, then $$$\mathrm{maxf}_1 \le n/2-1 = n_{\mathrm{new}}/2$$$.
• If $$$\mathrm{maxf}_1 = n/2$$$ and $$$\mathrm{maxf}_2 \lt 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 \lt n$$$, we can do an operation and keep the first condition satisfied. Thus, we can do operations while $$$n/2 \lt n\ \Leftrightarrow\ 0 \lt n/2\ \Leftrightarrow\ n \gt 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 \gt 1$$$, we can do an operation such that after the operation, $$$\mathrm{maxf}_1 \le \lceil n/2\rceil$$$.

Proof:

• If $$$\mathrm{maxf}_1 \lt \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 \lt \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 \lt \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 \gt n$$$, which is not possible.

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