424. Longest Repeating Character Replacement
Вам дана строка s и целое число k. Вы можете выбрать любой символ строки и заменить его на любой другой заглавный английский символ. Вы можете выполнить эту операцию не более k раз.
Верните длину самой длинной подстроки, содержащей одну и ту же букву, которую можно получить после выполнения вышеуказанных операций.
Пример:
Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.
C# решение
сопоставлено/оригиналpublic class Solution {
public int CharacterReplacement(string s, int k) {
int lo = 1;
int hi = s.Length + 1;
while (lo + 1 < hi) {
int mid = lo + (hi - lo) / 2;
if (CanMakeValidSubstring(s, mid, k)) {
lo = mid;
} else {
hi = mid;
}
}
return lo;
}
private bool CanMakeValidSubstring(string s, int substringLength, int k) {
int[] freqMap = new int[26];
int maxFrequency = 0;
int start = 0;
for (int end = 0; end < s.Length; end++) {
freqMap[s[end] - 'A']++;
if (end + 1 - start > substringLength) {
freqMap[s[start] - 'A']--;
start++;
}
maxFrequency = Math.Max(maxFrequency, freqMap[s[end] - 'A']);
if (substringLength - maxFrequency <= k) {
return true;
}
}
return false;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int CharacterReplacement(string s, int k) {
int lo = 1;
int hi = s.size() + 1;
while (lo + 1 < hi) {
int mid = lo + (hi - lo) / 2;
if (CanMakeValidSubstring(s, mid, k)) {
lo = mid;
} else {
hi = mid;
}
}
return lo;
}
private bool CanMakeValidSubstring(string s, int substringLength, int k) {
vector<int>& freqMap = new int[26];
int maxFrequency = 0;
int start = 0;
for (int end = 0; end < s.size(); end++) {
freqMap[s[end] - 'A']++;
if (end + 1 - start > substringLength) {
freqMap[s[start] - 'A']--;
start++;
}
maxFrequency = max(maxFrequency, freqMap[s[end] - 'A']);
if (substringLength - maxFrequency <= k) {
return true;
}
}
return false;
}
}Java решение
сопоставлено/оригиналclass Solution {
public int characterReplacement(String s, int k) {
int lo = 1;
int hi = s.length() + 1;
while (lo + 1 < hi) {
int mid = lo + (hi - lo) / 2;
if (canMakeValidSubstring(s, mid, k)) {
lo = mid;
} else {
hi = mid;
}
}
return lo;
}
private boolean canMakeValidSubstring(String s, int substringLength, int k) {
int[] freqMap = new int[26];
int maxFrequency = 0;
int start = 0;
for (int end = 0; end < s.length(); end++) {
freqMap[s.charAt(end) - 'A']++;
if (end + 1 - start > substringLength) {
freqMap[s.charAt(start) - 'A']--;
start++;
}
maxFrequency = Math.max(maxFrequency, freqMap[s.charAt(end) - 'A']);
if (substringLength - maxFrequency <= k) {
return true;
}
}
return false;
}
}JavaScript решение
сопоставлено/оригиналclass Solution {
characterReplacement(s, k) {
let lo = 1, hi = s.length + 1;
while (lo + 1 < hi) {
let mid = lo + Math.floor((hi - lo) / 2);
if (this.canMakeValidSubstring(s, mid, k)) {
lo = mid;
} else {
hi = mid;
}
}
return lo;
}
canMakeValidSubstring(s, substringLength, k) {
let freqMap = new Array(26).fill(0);
let maxFrequency = 0;
let start = 0;
for (let end = 0; end < s.length; end++) {
freqMap[s.charCodeAt(end) - 65]++;
if (end + 1 - start > substringLength) {
freqMap[s.charCodeAt(start) - 65]--;
start++;
}
maxFrequency = Math.max(maxFrequency, freqMap[s.charCodeAt(end) - 65]);
if (substringLength - maxFrequency <= k) {
return true;
}
}
return false;
}
}Python решение
сопоставлено/оригиналclass Solution:
def characterReplacement(self, s: str, k: int) -> int:
lo, hi = 1, len(s) + 1
while lo + 1 < hi:
mid = lo + (hi - lo) // 2
if self.canMakeValidSubstring(s, mid, k):
lo = mid
else:
hi = mid
return lo
def canMakeValidSubstring(self, s: str, substringLength: int, k: int) -> bool:
freqMap = [0] * 26
maxFrequency = 0
start = 0
for end in range(len(s)):
freqMap[ord(s[end]) - ord('A')] += 1
if end + 1 - start > substringLength:
freqMap[ord(s[start]) - ord('A')] -= 1
start += 1
maxFrequency = max(maxFrequency, freqMap[ord(s[end]) - ord('A')])
if substringLength - maxFrequency <= k:
return True
return FalseGo решение
сопоставлено/оригиналpackage main
func characterReplacement(s string, k int) int {
lo, hi := 1, len(s)+1
for lo + 1 < hi {
mid := lo + (hi - lo) / 2
if canMakeValidSubstring(s, mid, k) {
lo = mid
} else {
hi = mid
}
}
return lo
}
func canMakeValidSubstring(s string, substringLength, k int) bool {
freqMap := make([]int, 26)
maxFrequency := 0
start := 0
for end := 0; end < len(s); end++ {
freqMap[s[end] - 'A']++
if end + 1 - start > substringLength {
freqMap[s[start] - 'A']--
start++
}
if freqMap[s[end] - 'A'] > maxFrequency {
maxFrequency = freqMap[s[end] - 'A']
}
if substringLength - maxFrequency <= k {
return true
}
}
return false
}Algorithm
1⃣Определите диапазон поиска. Минимальная длина подстроки с одинаковыми символами всегда равна 1 (назовем ее min), а максимальная длина подстроки может быть равна длине данной строки (назовем ее max). Ответ будет лежать в диапазоне [min, max] (включительно).
2⃣Инициализируйте две переменные lo и hi для бинарного поиска. lo всегда указывает на длину допустимой строки, а hi - на недопустимую длину. Изначально lo равно 1, а hi равно max+1.
3⃣Выполните бинарный поиск, чтобы найти максимальное значение lo, которое представляет самую длинную допустимую подстроку. В конце lo будет содержать ответ, а hi будет на единицу больше lo.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.