LC: Longest Substring with At Most Two Distinct Characters - spiralgo/algorithms GitHub Wiki

Longest Substring with At Most Two Distinct Characters

The Essence:

When there is a substring currently consisting of two characters and a new substring with a third character is appended, the length of the next substring with two distinct characters will be the length of the substring with the last character in the previous plus the new character.

"abbabb" + "c" -> "bbc"

Thus, to add to calculate the current length in such a case, the algorithm needs to keep track of the index of the first character as well as the index of the second character. The length can be calculated with rearranging of the indices.

Details: Two pointers a and b that keep tracks of the last index occurrence of the two characters is sufficient. The running length is incremented as long as the two characters are encountered. When new a character is encountered, the one with the latest index should be counted for the new running length.