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.

Example 1:

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

Example 2:

Input: str="abbcb", k=1  
Output: 4  
Explanation: Replace the 'c' with 'b' to have a longest repeating substring "bbbb".

Example 3:

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

Constraints:

• 1 <= str.length <= 10^5
• s consists of only lowercase English letters.
• 0 <= k <= s.length

Solution

To solve this problem, we can use a sliding window technique. The idea is to maintain a window that can contain up to k characters that are different from the most frequent character in the current window. By doing so, we maximize the length of the window while keeping the number of changes within the allowed limit. This approach works because the window will only shrink when the number of characters that need to be changed exceeds k.

The sliding window approach is efficient because it only requires a single pass through the string, making it suitable for handling large input sizes. Additionally, it uses a hashmap to keep track of the frequency of characters in the current window, ensuring that we can quickly determine the most frequent character. This combination of techniques ensures that the solution is both time and space efficient.

Step-by-step Algorithm

1. Initialize Variables

   • Start a window at the beginning of the string.
   • Set maxLength to 0 to keep track of the longest valid substring.
   • Use maxRepeatLetterCount to store the count of the most frequent character in the current window.
   • Use a HashMap letterFrequencyMap to store the frequency of each character in the current window.

2. Expand the Window

   • Iterate through the string using a loop with windowEnd ranging from 0 to the length of the string.
   • Add the character at windowEnd to the letterFrequencyMap and update its frequency.
   • Update maxRepeatLetterCount to be the maximum frequency of any character in the current window.

3. Shrink the Window if Necessary

   • If the number of characters that need to be replaced (windowEnd - windowStart + 1 - maxRepeatLetterCount) exceeds k, shrink the window from the left by incrementing windowStart.
   • Adjust the frequency of the character that is left out of the window.

4. Update the Maximum Length

   • Calculate the current window size and update maxLength if the current window size is larger.

5. Return the Result

   • After the loop, maxLength will hold the length of the longest substring where up to k characters can be replaced to make all characters the same.

Algorithm Walkthrough

Let's go through the example str = "aabccbb", k = 2 step by step.

1. Initialization

   • windowStart = 0, maxLength = 0, maxRepeatLetterCount = 0
   • letterFrequencyMap = {}

2. Expand the Window

   • Iteration 1

     • windowEnd = 0, rightChar = 'a'
     • Update letterFrequencyMap = {'a': 1}
     • maxRepeatLetterCount = 1
     • Current window size = windowEnd - windowStart + 1 = 1
     • windowEnd - windowStart + 1 - maxRepeatLetterCount = 1 - 1 = 0 (<= k)
     • Update maxLength = 1

   • Iteration 2

     • windowEnd = 1, rightChar = 'a'
     • Update letterFrequencyMap = {'a': 2}
     • maxRepeatLetterCount = 2
     • Current window size = windowEnd - windowStart + 1 = 2
     • windowEnd - windowStart + 1 - maxRepeatLetterCount = 2 - 2 = 0 (<= k)
     • Update maxLength = 2

   • Iteration 3

     • windowEnd = 2, rightChar = 'b'
     • Update letterFrequencyMap = {'a': 2, 'b': 1}
     • maxRepeatLetterCount = 2
     • Current window size = windowEnd - windowStart + 1 = 3
     • windowEnd - windowStart + 1 - maxRepeatLetterCount = 3 - 2 = 1 (<= k)
     • Update maxLength = 3

   • Iteration 4

     • windowEnd = 3, rightChar = 'c'
     • Update letterFrequencyMap = {'a': 2, 'b': 1, 'c': 1}
     • maxRepeatLetterCount = 2
     • Current window size = windowEnd - windowStart + 1 = 4
     • windowEnd - windowStart + 1 - maxRepeatLetterCount = 4 - 2 = 2 (<= k)
     • Update maxLength = 4

   • Iteration 5

     • windowEnd = 4, rightChar = 'c'
     • Update letterFrequencyMap = {'a': 2, 'b': 1, 'c': 2}
     • maxRepeatLetterCount = 2
     • Current window size = windowEnd - windowStart + 1 = 5
     • windowEnd - windowStart + 1 - maxRepeatLetterCount = 5 - 2 = 3 (> k)
     • Shrink window: windowStart = 1
     • Update letterFrequencyMap = {'a': 1, 'b': 1, 'c': 2}
     • Current window size after shrinking = windowEnd - windowStart + 1 = 4

   • Iteration 6

     • windowEnd = 5, rightChar = 'b'
     • Update letterFrequencyMap = {'a': 1, 'b': 2, 'c': 2}
     • maxRepeatLetterCount = 2
     • Current window size = windowEnd - windowStart + 1 = 5
     • windowEnd - windowStart + 1 - maxRepeatLetterCount = 5 - 2 = 3 (> k)
     • Shrink window: windowStart = 2
     • Update letterFrequencyMap = {'a': 0, 'b': 2, 'c': 2}
     • Current window size after shrinking = windowEnd - windowStart + 1 = 4

   • Iteration 7

     • windowEnd = 6, rightChar = 'b'
     • Update letterFrequencyMap = {'a': 0, 'b': 3, 'c': 2}
     • maxRepeatLetterCount = 3
     • Current window size = windowEnd - windowStart + 1 = 5
     • windowEnd - windowStart + 1 - maxRepeatLetterCount = 5 - 3 = 2 (<= k)
     • Update maxLength = 5

• The maximum length of the substring with up to 2 character replacements is 5 for the input string aabccbb. The valid substring is "bccbb" or "abccb".

Code  

Here is what our algorithm will look like:

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

Space Complexity

As we expect 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).