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

Longest Substring with At Most K Distinct Characters

The Essence:

When adding a character to a substring makes it have k+1 distinct characters, then the left boundary of this substring should be shrinked, until the count of some other character in the substring reaches 0. After that, the procedure can compare and try to append a new character (expand the right boundary).

Details:

For the implementation, simply keeping an array or a map for counting the characters is sufficient. There should also be a left and right index to depict substring boundaries. The current number of distinct character should also be kept.

The usage of left and right indices is a common technique in array and string problems. The problem-solvers should try to learn about such techniques. Other problems would render helpful in this.

Further explanation and the code implementation can be found here: https://github.com/spiralgo/algorithms/pull/123