Finding length of longest substring after K replacements in given string

0 / 126
substring replacement

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: String=“aabccbb”, k=2

Output: 5

Explanation: Replace the two ‘c’ with ‘b’ to have a longest repeating substring “bbbbb”.
 
Example 2:

 

Input: String=“abbcb”, k=1

Output: 4

Explanation: Replace the ‘c’ with ‘b’ to have a longest repeating substring “bbbb”.

 

 

Example 3:

 

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

 

Javascript code below:-

 

<script>

function length_of_longest_substring(str, k) {
  // TODO: Write your code here
  var windowStart = 0;
  var maxLetterCount = 0;
  var maxLength = 0;
  var charFreqMap = {};

  for (var windowEnd = 0; windowEnd < str.length; windowEnd++) {
    if (typeof charFreqMap[str[windowEnd]] === 'undefined') {
      charFreqMap[str[windowEnd]] = 0;
    }
    charFreqMap[str[windowEnd]]++;

    maxLetterCount = Math.max(windowStart, charFreqMap[str[windowEnd]]);

    if(windowEnd - windowStart + 1 - maxLetterCount > k) {
      charFreqMap[str[windowStart]]--;
      windowStart++;
    }

  maxLength = Math.max(maxLength, windowEnd - windowStart + 1);

  }

  return maxLength;
};

document.write(length_of_longest_substring('aabccbb', 2)+'<br/>');
document.write(length_of_longest_substring('abbcb', 1)+'<br/>');
document.write(length_of_longest_substring('abccde', 1)+'<br/>');

</script>

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 Map, which is asymptotically equal to O(1).

 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.

Related Posts