Longest Substring with Same Letters after Replacement

Hard·Tagsstringsliding-windowhash-table

Problem Statement

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

Example 1

Input

k: 2, str: "aabccbb"

Output

"5"

Why

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

Example 2

Input

k: 1, str: "abbcb"

Output

"4"

Why

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

Example 3

Input

k: 1, str: "abccde"

Output

"3"

Why

Replace the 'b' or 'd' with 'c' to have the longest repeating substring "ccc".

Constraints

•1 <= str.length <= 100000
•1 <= k <= str.length
•The string consists of standard lowercase English characters.

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

Iterate through the string to add one letter at a time to the window. Keep track of the frequency of each letter.

Hint 2

Also, keep track of the maximum frequency of a single letter in the current window (let's call it `maxRepeatLetterCount`).

Hint 3

If the current window size minus `maxRepeatLetterCount` is greater than `k`, it means we have more than `k` letters that need to be replaced. At this point, we should shrink the window from the left.