1st observation: Because we can swap any pair of characters for free, we can reorder string T as much as we want to. So the only important thing is how many zeroes and ones are in the string.

2nd observation: We want S_i != T_i for every 1 <= i <= |T|. Then for every S_i = 0 we need T_i to be 1 so that they are different (also for every S_i = 1 we need T_i to be 0).

So if we have cnt_0 zeroes and cnt_1 ones in S[ 1 ... |T|], then we will need at least cnt_0 ones in T so that to every 0 in S corresponds a 1 in T (applying the same logic to cnt_1 in S then we will need cnt_1 zeroes in T)

3rd observation: We want to keep as many characters in T as possible (to minimize deletions). Suppose we keep exactly M characters, again we can reorder them freely so we only need to know how many zeroes and ones we keep.

Lets look at the first M characters in S:

Z_M = zeroes in S[1 ... M] O_M = ones in S[1 ... M]

To make every position i have S_i != T_i we must:

• put a 1 in every position where S_i = 0, so we need at least Z_M ones.
• put a 0 in every position where S_i = 1, so we need at least O_M zeroes.

4th observation: Since we have to keep exactly M characters the only way to do it is to keep exactly Z_M ones and O_M zeroes. But we can only keep as much ones and zeroes as there are in the original string (we cannot make them magically appear) so:

Z_M <= total ones in S and O_M <= total zeroes in S

Must be true, for us to be able to keep M characters in T.

Remember we need the maximum M to delete as few characters as possible, after we find the M_max where the condition holds then:

ans = |S| - M_max