Longest Repeating Substring

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
74 upvotes
Asked in companies
IBMMakeMyTripCIS - Cyber Infrastructure

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1 :

ABCCAA
2

Sample Output 1 :

4

Explanation for Sample Input 1 :

“AAAA” and “CCCC” are the longest repeating substring we can get after performing 2 operations.

Sample Input 2 :

ABA
3

Sample Output 2 :

3

Constraints :

1 <= |s| <= 10^5
0 <= k <= |s|
's' consists of only uppercase English letters.


where |s| is the length of the given string.

Time Limit: 1sec
Hint

For each substring, check if it can be the longest repeating substring after performing at most K operations.

Approaches (2)
Brute Force

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. 

Time Complexity

O(N^2), Where N is the size of the given array.
 

It takes O(N^2) to consider every substring. Thus, the final time complexity is O(N^2).

Space Complexity

O(1), constant space is used.
 

We are making an array of size 26 (constant) to store the count of characters. Thus, the final space complexity is O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Longest Repeating Substring
Full screen
Console