Longest Repeating Substring

Moderate

0/80

Average time to solve is 10m

Contributed by

62 upvotes

Asked in companies

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 :

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 :

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

Console