Задача: 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 {
    function characterReplacement
class Solution {
    function characterReplacement($s, $k) {
        $lo = 1;
        $hi = strlen($s) + 1;

        while ($lo + 1 < $hi) {
            $mid = $lo + intval(($hi - $lo) / 2);
            if ($this->canMakeValidSubstring($s, $mid, $k)) {
                $lo = $mid;
            } else {
                $hi = $mid;
            }
        }

        return $lo;
    }

    private function canMakeValidSubstring($s, $substringLength, $k) {
        $freqMap = array_fill(0, 26, 0);
        $maxFrequency = 0;
        $start = 0;

        for ($end = 0; $end < strlen($s); $end++) {
            $freqMap[ord($s[$end]) - ord('A')]++;

            if ($end + 1 - $start > $substringLength) {
                $freqMap[ord($s[$start]) - ord('A')]--;
                $start++;
            }

            $maxFrequency = max($maxFrequency, $freqMap[ord($s[$end]) - ord('A')]);
            if ($substringLength - $maxFrequency <= $k) {
                return true;
            }
        }

        return false;
    }
}

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