Last Updated: 14 Dec, 2020
Longest Repeating Substring
Moderate
Asked in companies
You are given a string 'str' of length 'N'. You can perform at most 'k' operations on this string. In one operation, you can choose any character of the string and change it to any other uppercase English alphabet character.
Return the length of the longest substring containing same characters after performing the above operations.
For example :
Input:
str="AABC" k=1
Output:3
Explanation: Replace 'B' with 'A', we will get "AAAC" and the longest substring with same character is "AAA" of length 3.
Input Format :
The first line contains a string 'str' consisting of uppercase English alphabet letters.
The second line contains a positive integer 'k', which represents the maximum number of operations you can perform.
Output Format :
The output contains the length of the longest repeating substring with the same characters that we can obtain after performing 'k' operations.
Note :
You do need to print anything, it has already been taken care of. Just implement the given function.
Approaches
In this approach, we will consider every substring and check if it can be the longest repeating substring. Let’s say we have a variable ‘longestSubstring’ that stores the length of the longest repeating substring.
We can convert a substring into a repeating substring if, (L - MX) <= K (where ‘L’ is the length of substring and ‘MX’ is the count of the character which occurs maximum times in this substring).
For every substring, we will make a ‘count’ array of size 26 that will store the count of each character in the substring. Then, we can check if it is the longest repeating substring encountered till now. If it is, we update ‘longestSubstring’ to the length of this string.
The idea here is to use the sliding window technique. We will call a window stable if we can convert the string in this window into a repeating string. If we add a new character at the end of the window, then we have to remove characters from the beginning until the window becomes stable.
We can convert a substring into a repeating substring if, (L - MX) <= K (where ‘L’ is the length of substring and ‘MX’ is the count of the character which occurs maximum times in substring).
We define the window bounded by two pointers ‘i’ and ‘j’ and the window size is (j-i+1). We will initialize the pointers pointing to the first character in the string, then we will increment ‘j’ and if the window becomes unstable, we will increment ‘i’ until the window becomes stable. To store the count of characters in the window we will make an array of size 26 (number of lowercase English alphabet letters).