JavaScript
class Solution {
// Solution using two pointers and Map
characterReplacement(s, k) {
const count = new Map();
let maxCount = 0;
let maxLength = 0;
let left = 0;
for (let right = 0; right < s.length; right++) {
count.set(s[right], (count.get(s[right]) || 0) + 1);
maxCount = Math.max(maxCount, count.get(s[right]));
while ((right - left + 1) - maxCount > k) {
count.set(s[left], count.get(s[left]) - 1);
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
// Time: O(n), Space: O(1)
// Alternative solution using array
characterReplacementArray(s, k) {
const count = new Array(26).fill(0);
let maxCount = 0;
let left = 0;
let result = 0;
for (let right = 0; right < s.length; right++) {
count[s.charCodeAt(right) - 65]++;
maxCount = Math.max(maxCount, count[s.charCodeAt(right) - 65]);
if ((right - left + 1) - maxCount > k) {
count[s.charCodeAt(left) - 65]--;
left++;
}
result = Math.max(result, right - left + 1);
}
return result;
}
// Time: O(n), Space: O(1)
}
Java
class Solution {
// Solution using frequency array
public int characterReplacement(String s, int k) {
int[] count = new int[26];
int maxCount = 0;
int left = 0;
int maxLength = 0;
for (int right = 0; right < s.length(); right++) {
count[s.charAt(right) - 'A']++;
maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);
if ((right - left + 1) - maxCount > k) {
count[s.charAt(left) - 'A']--;
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
// Time: O(n), Space: O(1)
// Solution using HashMap
public int characterReplacementMap(String s, int k) {
Map<Character, Integer> count = new HashMap<>();
int maxCount = 0;
int left = 0;
int result = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
count.put(c, count.getOrDefault(c, 0) + 1);
maxCount = Math.max(maxCount, count.get(c));
while ((right - left + 1) - maxCount > k) {
char leftChar = s.charAt(left);
count.put(leftChar, count.get(leftChar) - 1);
left++;
}
result = Math.max(result, right - left + 1);
}
return result;
}
// Time: O(n), Space: O(1)
}
Python
class Solution:
# Solution using dictionary
def characterReplacement(self, s: str, k: int) -> int:
count = {}
max_count = 0
left = 0
result = 0
for right in range(len(s)):
count[s[right]] = count.get(s[right], 0) + 1
max_count = max(max_count, count[s[right]])
if (right - left + 1) - max_count > k:
count[s[left]] -= 1
left += 1
result = max(result, right - left + 1)
return result
# Time: O(n), Space: O(1)
# Solution using array
def characterReplacement_array(self, s: str, k: int) -> int:
count = [0] * 26
max_count = left = result = 0
for right in range(len(s)):
count[ord(s[right]) - ord('A')] += 1
max_count = max(max_count, count[ord(s[right]) - ord('A')])
if (right - left + 1) - max_count > k:
count[ord(s[left]) - ord('A')] -= 1
left += 1
result = max(result, right - left + 1)
return result
# Time: O(n), Space: O(1)
All presented solutions use the sliding window technique and have linear time complexity O(n), where n is the length of the input string. Space complexity is O(1) since we use a fixed amount of additional memory (26 alphabet characters).