Problem:
Given a string s that consists of only uppercase English letters, you can perform at most k operations on that string.In one operation, you can choose any character of the string and change it to any other uppercase English character.
Find the length of the longest sub-string containing all repeating letters you can get after performing the above operations.
Note:
Both the string's length and k will not exceed 104.
Example 1:
Input:
s = "ABAB", k = 2
Output:
4
Explanation:
Replace the two 'A's with two 'B's or vice versa.
Example 2:
Input:
s = "AABABBA", k = 1
Output:
4
Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
Solution:
We can use a sliding window, the right edge increase 1 at each step. At each step, we get the sliding window size r - l + 1, we also update the character frequency freq[c] and find the character with the highest frequency maxLen, for all the characters in the sliding window. If r -l + 1 - maxLen <= k, we are able to change all the other characters in the sliding window to the highest frequency character. As a result, we update the result for the current window size, then go to the next step.
If r -l + 1 - maxLen > k, we should stop expanding, and shrink the sliding window to restore the constraint r -l + 1 - maxLen <= k. We move the left edge one step at a time. At each step, we get the sliding window size r - l + 1, we also update the character frequency freq[c] and find the character with the highest frequency maxLen, for all the characters in the sliding window.
import java.util.stream.*;
class Solution {
public static void main(String...args) {
System.out.println(longestSub("ABAB", 2));
System.out.println(longestSub("ABAB", 3));
System.out.println(longestSub("ABAB", 1));
System.out.println(longestSub("ABAB", 10));
}
//AABABBA 1 ---- A 1, B 2
// .
// .
public static int longestSub(String str, int k) {//
int l = 0; //sliding window left pointer
int maxLen = 0; //max repeating character in the window
int[] freq = new int['Z' - 'A' + 1];
int result = 0;
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
freq[c - 'A']++;
maxLen = Math.max(maxLen, freq[c - 'A']);
if(i - l + 1 - maxLen <= k) {
result = Math.max(result, i - l + 1);
}
while(i - l + 1 - maxLen > k) {
freq[str.charAt(l++) - 'A']--;
maxLen = IntStream.of(freq).max().getAsInt();
}
}
return result;
}
}
class Solution {
public static void main(String...args) {
System.out.println(longestSub("ABAB", 2));
System.out.println(longestSub("ABAB", 3));
System.out.println(longestSub("ABAB", 1));
System.out.println(longestSub("ABAB", 10));
}
//AABABBA 1 ---- A 1, B 2
// .
// .
public static int longestSub(String str, int k) {//
int l = 0; //sliding window left pointer
int maxLen = 0; //max repeating character in the window
int[] freq = new int['Z' - 'A' + 1];
int result = 0;
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
freq[c - 'A']++;
maxLen = Math.max(maxLen, freq[c - 'A']);
if(i - l + 1 - maxLen <= k) {
result = Math.max(result, i - l + 1);
}
while(i - l + 1 - maxLen > k) {
freq[str.charAt(l++) - 'A']--;
maxLen = IntStream.of(freq).max().getAsInt();
}
}
return result;
}
}
The time complexity is O(N), the left edge and right edge iterate the string length at most once. When we move the left edge, for each step, we need to find the maxLen with maxLen = IntStream.of(freq).max().getAsInt(); the cost is 26 comparisons at most.
The space complexity is O(1), the character frequency counting array has size 26.
The space complexity is O(1), the character frequency counting array has size 26.
