Problem Statement:
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.
Examples:
Example 1:
Input: s = “ABAB”, k = 2
Output: 2
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. There may exists other ways to achieve this answer too.
Constraints:
0 <= s.length <= 105sconsists of English letters, digits, symbols and spaces.0 <= k <= s.length
Approach
- Use a sliding window with two pointers
iandjto represent the current window. - Maintain a frequency array
mapof size 26 for uppercase letters. - At each step, check if the window is valid:
- A window is valid if total letters - max frequent letter ≤
k(i.e., we can change ≤ k chars to make all same).
- A window is valid if total letters - max frequent letter ≤
-
If valid, expand the window
(j++), else shrink from left(i++). - Track the maximum valid window size throughout.
Time Complexity:
Time Complexity = O(26 x n) ≈ O(n)
Space Complexity:
Space Complexity = O(m)
Dry Run
Input: s = "AABABBA", k = 1
Initialize: i = 0, j = 0 map = Array(26).fill(0) map['A'] → map[0] = 1 (first char) maxWindow = 0 // Start while loop: j < s.length j = 0 → s[j] = 'A' → map = [1,...] → isWindowValid(map, 1): totalCount = 1, maxCount = 1 → 1 - 1 ≤ 1 → valid → maxWindow = max(0, 0-0+1) = 1 → j++, j = 1 → map['A']++ → map[0] = 2 j = 1 → s[j] = 'A' → map = [2,...] → isWindowValid(map, 1): totalCount = 2, maxCount = 2 → 2 - 2 ≤ 1 → valid → maxWindow = max(1, 1-0+1) = 2 → j++, j = 2 → map['B']++ → map[1] = 1 j = 2 → s[j] = 'B' → map = [2,1,...] → isWindowValid(map, 1): totalCount = 3, maxCount = 2 → 3 - 2 = 1 ≤ 1 → valid → maxWindow = max(2, 2-0+1) = 3 → j++, j = 3 → map['A']++ → map[0] = 3 j = 3 → s[j] = 'A' → map = [3,1,...] → isWindowValid(map, 1): totalCount = 4, maxCount = 3 → 4 - 3 = 1 ≤ 1 → valid → maxWindow = max(3, 3-0+1) = 4 → j++, j = 4 → map['B']++ → map[1] = 2 j = 4 → s[j] = 'B' → map = [3,2,...] → isWindowValid(map, 1): totalCount = 5, maxCount = 3 → 5 - 3 = 2 > 1 → invalid → shrink window: → map['A']-- → map[0] = 2 → i++, i = 1 → isWindowValid(map, 1): totalCount = 4, maxCount = 2 → 4 - 2 = 2 > 1 → invalid → map['A']-- → map[0] = 1 → i++, i = 2 → isWindowValid(map, 1): totalCount = 3, maxCount = 2 → 3 - 2 = 1 → valid → maxWindow = max(4, 4-2+1) = 4 → j++, j = 5 → map['B']++ → map[1] = 3 j = 5 → s[j] = 'B' → map = [1,3,...] → isWindowValid(map, 1): totalCount = 4, maxCount = 3 → 4 - 3 = 1 → valid → maxWindow = max(4, 5-2+1) = 4 → j++, j = 6 → map['A']++ → map[0] = 2 j = 6 → s[j] = 'A' → map = [2,3,...] → isWindowValid(map, 1): totalCount = 5, maxCount = 3 → 5 - 3 = 2 > 1 → invalid → shrink window: → map['B']-- → map[1] = 2 → i++, i = 3 → isWindowValid(map, 1): totalCount = 4, maxCount = 2 → 4 - 2 = 2 > 1 → invalid → map['A']-- → map[0] = 1 → i++, i = 4 → isWindowValid(map, 1): totalCount = 3, maxCount = 2 → 3 - 2 = 1 → valid → maxWindow = max(4, 6-4+1) = 4 → j++, j = 7 → exit loop Final map: [1,2,...] Final maxWindow: 4
Output: Result: 4
var characterReplacement = function(s, k) {
let i = 0, j = 0;
let map = Array(26).fill(0);
map[s.charCodeAt(0) - 65] = 1;
let maxWindow = 0;
while (j < s.length) {
if (isWindowValid(map, k)) {
maxWindow = Math.max(maxWindow, j - i + 1);
++j;
++map[s.charCodeAt(j) - 65];
} else {
--map[s.charCodeAt(i) - 65];
++i;
}
}
return maxWindow;
};
var isWindowValid = function(map, k) {
let totalCount = 0;
let maxCount = 0;
for (let i = 0; i < 26; i++) {
totalCount += map[i];
maxCount = Math.max(maxCount, map[i]);
}
return (totalCount - maxCount <= k);
};
def is_window_valid(counts, k):
total = sum(counts)
max_count = max(counts)
return (total - max_count) <= k
def characterReplacement(s, k):
i = j = 0
counts = [0] * 26
counts[ord(s[0]) - ord('A')] = 1
max_window = 0
while j < len(s):
if is_window_valid(counts, k):
max_window = max(max_window, j - i + 1)
j += 1
if j < len(s):
counts[ord(s[j]) - ord('A')] += 1
else:
counts[ord(s[i]) - ord('A')] -= 1
i += 1
return max_window
import java.util.HashMap;
public class Solution {
public int characterReplacement(String s, int k) {
int[] map = new int[26];
int i = 0, j = 0, maxWindow = 0;
map[s.charAt(0) - 'A'] = 1;
while(j < s.length()) {
if(isWindowValid(map, k)) {
maxWindow = Math.max(maxWindow, j - i + 1);
++j;
if(j < s.length()) map[s.charAt(j) - 'A']++;
} else {
map[s.charAt(i) - 'A']--;
++i;
}
}
return maxWindow;
}
private boolean isWindowValid(int[] map, int k) {
int totalCount = 0, maxCount = 0;
for(int count : map) {
totalCount += count;
maxCount = Math.max(maxCount, count);
}
return (totalCount - maxCount <= k);
}
}
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
bool isWindowValid(vector& map, int k) {
int totalCount = 0, maxCount = 0;
for(int i = 0; i < 26; i++) {
totalCount += map[i];
maxCount = max(maxCount, map[i]);
}
return (totalCount - maxCount <= k);
}
int characterReplacement(string s, int k) {
int i = 0, j = 0, maxWindow = 0;
vector map(26, 0);
map[s[0] - 'A'] = 1;
while(j < s.length()) {
if(isWindowValid(map, k)) {
maxWindow = max(maxWindow, j - i + 1);
++j;
if(j < s.length()) ++map[s[j] - 'A'];
} else {
--map[s[i] - 'A'];
++i;
}
}
return maxWindow;
}
#include <stdio.h>
#include <string.h>
int isWindowValid(int map[26], int k) {
int totalCount = 0, maxCount = 0;
for(int i = 0; i < 26; i++) {
totalCount += map[i];
if(map[i] > maxCount) maxCount = map[i];
}
return (totalCount - maxCount <= k);
}
int characterReplacement(const char* s, int k) {
int map[26] = {0};
int i = 0, j = 0, maxWindow = 0;
map[s[0] - 'A'] = 1;
int len = strlen(s);
while(j < len) {
if(isWindowValid(map, k)) {
if(maxWindow < j - i + 1) maxWindow = j - i + 1;
++j;
if(j < len) map[s[j] - 'A']++;
} else {
map[s[i] - 'A']--;
++i;
}
}
return maxWindow;
}
using System;
public class Solution {
public int CharacterReplacement(string s, int k) {
int[] map = new int[26];
int i = 0, j = 0, maxWindow = 0;
map[s[0] - 'A'] = 1;
while (j < s.Length) {
if (IsWindowValid(map, k)) {
maxWindow = Math.Max(maxWindow, j - i + 1);
++j;
if (j < s.Length) map[s[j] - 'A']++;
} else {
map[s[i] - 'A']--;
++i;
}
}
return maxWindow;
}
private bool IsWindowValid(int[] map, int k) {
int totalCount = 0, maxCount = 0;
foreach (int count in map) {
totalCount += count;
maxCount = Math.Max(maxCount, count);
}
return (totalCount - maxCount <= k);
}
}
