Задача: 424. Longest Repeating Character Replacement
Сложность: medium

Вам дана строка s и целое число k. Вы можете выбрать любой символ строки и заменить его на любой другой заглавный английский символ. Вы можете выполнить эту операцию не более k раз.

Верните длину самой длинной подстроки, содержащей одну и ту же букву, которую можно получить после выполнения вышеуказанных операций.

Пример:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

👨‍💻 Алгоритм:

1⃣Определите диапазон поиска. Минимальная длина подстроки с одинаковыми символами всегда равна 1 (назовем ее min), а максимальная длина подстроки может быть равна длине данной строки (назовем ее max). Ответ будет лежать в диапазоне [min, max] (включительно).

2⃣Инициализируйте две переменные lo и hi для бинарного поиска. lo всегда указывает на длину допустимой строки, а hi - на недопустимую длину. Изначально lo равно 1, а hi равно max+1.

3⃣Выполните бинарный поиск, чтобы найти максимальное значение lo, которое представляет самую длинную допустимую подстроку. В конце lo будет содержать ответ, а hi будет на единицу больше lo.

😎 Решение:

class Solution {
    func characterReplacement(_ s: String, _ k: Int) -> Int {
        var lo = 1
        var hi = s.count + 1

        while lo + 1 < hi {
            let mid = lo + (hi - lo) / 2
            if canMakeValidSubstring(s, mid, k) {
                lo = mid
            } else {
                hi = mid
            }
        }
        return lo
    }

    private func canMakeValidSubstring(_ s: String, _ substringLength: Int, _ k: Int) -> Bool {
        var freqMap = [Int](repeating: 0, count: 26)
        var maxFrequency = 0
        let sArray = Array(s)
        var start = 0

        for end in 0..<sArray.count {
            freqMap[Int(sArray[end].asciiValue! - Character("A").asciiValue!)] += 1

            if end + 1 - start > substringLength {
                freqMap[Int(sArray[start].asciiValue! - Character("A").asciiValue!)] -= 1
                start += 1
            }

            maxFrequency = max(maxFrequency, freqMap[Int(sArray[end].asciiValue! - Character("A").asciiValue!)])
            if substringLength - maxFrequency <= k {
                return true
            }
        }
        return false
    }
}

Ставь 👍 и забирай 📚 Базу знаний