JavaScript
class Solution {
// Решение с использованием двух указателей и 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;
}
// Время: O(n), Память: O(1)
// Альтернативное решение с использованием массива
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;
}
// Время: O(n), Память: O(1)
}
Java
class Solution {
// Решение с использованием массива частот
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;
}
// Время: O(n), Память: O(1)
// Решение с использованием 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;
}
// Время: O(n), Память: O(1)
}
Python
class Solution:
# Решение с использованием словаря
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
# Время: O(n), Память: O(1)
# Решение с использованием массива
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
# Время: O(n), Память: O(1)
Все представленные решения используют технику скользящего окна и имеют линейную временную сложность O(n), где n - длина входной строки. Пространственная сложность O(1), так как мы используем фиксированный размер дополнительной памяти (26 символов алфавита).