An informal proof of some sort:

When removing at only 1 position, which positions when removed will not be distinct? Take any 2 positions , when would they be equal? We get the following equalities:

for all

for all ()

for all

This shows that 2 positions are only equal if they are on the same equal group. So now we try to count by going over groups instead.

What about removing at only 2 positions? Again, take any 2 positions in different groups . Without loss of generality: and . When , and would have to be in the same group so we ignore this case. When things get a little interesting (note that case is the same as the only removing 1 character case):

for all

for all ()

for all ( and )

for all ()

for all

Unioning these equalities, if represents any character and and represent any 2 distinct characters, the string has the form: or . Ignoring equal groups, this means removing at adjacent positions on the same alternating character group will result in the same string.

My solution first counts the number of ways to choose 2 groups plus choosing 2 characters in the same group, then subtracts the length of each alternating character group minus 1 so that adjacent positions are only counted once per alternating character group to account for the overcounting.