Hints : Erase First or Second Letter
The final string can be classified into three different classes. What are they?
It can be a suffix of the original string.
...xyz
It can be a suffix plus an individual letter from the left.
...[c]...xyz
It can be a single letter.
...[c]...
Consider a suffix str[i...n]
.
We can take it alone (to form an element of class 1), or prepend a unique character from the left to get an element of class 2. However, the appended character should not be equal to str[i - 1]
, as the resulting string is anyway a suffix that would counted in the next iteration.
In the end, we add contribution of elements from class 3, i.e, single unique characters. Just make sure to not double count the suffix of length 1.