Longest substring with the same letters after replacement [Sliding Window]

This is a popular algorithmic problem that involves finding the longest substring containing the same letters after replacing a certain number of letters. The sliding window pattern is employed to solve the problem.

Try the problem on educative!

Although the solution is pretty descriptive on educative, the lack of visualization, a more step-by-step approach to the algorithm and a walkthrough with the sample I/O is what prompted me to write this post.

Sample I/O:

Input:

String="aabccbb", k=2

Output:

5

Explanation:

Replace the two 'c' with 'b' to have a longest repeating substring "bbbbb".

Similarly,

Input: String="abbcb", k=1
Output: 4
Explanation: Replace the 'c' with 'b' to have a longest repeating substring "bbbb'
Input: String="abccde", k=1
Output: 3
Explanation: Replace the 'b' or 'd' with 'c' to have the longest repeating substring "ccc".

Data structures:

• window_start = 0, the starting index of the sliding window
• max_length = 0, the maximum length of the substring; our result (the longest substring)
• max_repeat_letter_count = 0, the maximum count of the repeating characters.