This question is part of NeetCode150 series.
Problem Description
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
Example:
Input: s = “ABAB”, k = 2
Output: 4
Explanation: Replace the two ‘A’s with two ‘B’s or vice versa.
Solution
The main logic is that, if we have any string and the frequency of the element which occurs most numbers of times is X, then the number of operations needed to change other alphabets is = length of substring - X. If this is > k, then this is not a valid substring.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public int characterReplacement(String s, int k) {
int n = s.length();
//We will use this to store the frequency of each upper-case alphabet
//Note that the question mentions that the input string contains only uppercase alphabets
int[] frequency = new int[26];
int start = 0;
int maxLength = 0;
int maxFrequency = 0;
//We will start the window from [0,0]
for(int end=0; end<n; end++){
//Get the current character
char current = s.charAt(end);
//Increase the frequency of that character
//Here, A is at index 0, B is at index 1, C is at index 2, and so on...
frequency[current-'A']++;
//This part does the main trick for us. We maintain the max frequency while iterating the characters
//The main idea is: If the total length is x and the frequency of max occurring element in that substring is y
//then the number of changes required is: x-y
maxFrequency = Math.max(maxFrequency, frequency[current-'A']);
//Same as x-y explained above.
//Length of substring minus frequency of most occurring element
int diff = (end-start+1) - maxFrequency;
//If the difference is more than k, that substring is not a valid answer
//So, we decrease the count of start of the window
//And shift start to right
if(diff > k){
frequency[s.charAt(start)-'A']--;
start++;
}
//Update max length. Right of the windows will increase due to the for loop condition which is what we want
maxLength = Math.max(maxLength, end-start+1);
}
return maxLength;
}
}