"""
Given a string with lowercase letters only, if you are allowed to replace no
more than ‘k’ letters with any letter, find the length of the longest
substring having the same letters after replacement.

Examples
--------

Input: String="aabccbb", k=2
Output: 5
Explanation: Replace the two 'c' with 'b' to have a longest repeating substring "bbbbb".

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".

Solution
--------

This problem follows the Sliding Window pattern and we can use a similar
dynamic sliding window strategy as discussed in No-repeat Substring.
We can use a HashMap to count the frequency of each letter.

We’ll iterate through the string to add one letter at a time in the window.
We’ll also keep track of the count of the maximum repeating letter in any
window (let’s call it maxRepeatLetterCount). So at any time, we know that
we can have a window which has one letter repeating maxRepeatLetterCount
times, this means we should try to replace the remaining letters.
If we have more than ‘k’ remaining letters, we should shrink the window as
we are not allowed to replace more than ‘k’ letters.

Time Complexity
---------------

The time complexity of the above algorithm will be O(N) where ‘N’ is the number
of letters in the input string.

Space Complexity
----------------

As we are expecting only the lower case letters in the input string, we can
conclude that the space complexity will be O(26), to store each letter’s
frequency in the HashMap, which is asymptotically equal to O(1).

"""


def length_of_longest_substring(s, k):
    window_start = max_len = max_repeat_letter_count = 0
    freq_map = {}

    for window_end in range(len(s)):
        right_char = s[window_end]
        if right_char not in freq_map:
            freq_map[right_char] = 0
        freq_map[right_char] += 1
        max_repeat_letter_count = max(max_repeat_letter_count, freq_map[right_char])

        if (window_end - window_start + 1 - max_repeat_letter_count) > k:
            print(f"window_end={window_end}")
            left_char = s[window_start]
            freq_map[left_char] -= 1
            window_start += 1
        max_len = max(max_len, window_end - window_start + 1)
    return max_len


if __name__ == "__main__":
    print(length_of_longest_substring("aabccbb", 2))
    print(length_of_longest_substring("abbcb", 1))
    print(length_of_longest_substring("abccde", 1))
