Longest Repeating Character Replacement

+10

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

Верни длину самой длинной подстроки — последовательности соседних букв, — в которой после замен повторяется одна и та же буква.

Функция

characterReplacement(s: string, k: integer) → integer

sstring: строка заглавных букв
kinteger: максимальное количество букв, которые вы можете изменить
Возвращаетinteger: длина самой длинной подстроки из одной повторяющейся буквы, которую можно составить

Ограничения

1 ≤ s.length ≤ 5 × 10⁴
s содержит только заглавные английские буквы.
0 ≤ k ≤ s.length

Примеры

Ввод: s = "BAAACAB"k = 1
Вывод: 5
Пояснение: Замени C на A, и в индексах с 1 по 5 будет AAAAA. Для шести букв потребуются два изменения: в индексах с 0 по 5 находятся B и C, а в индексах с 1 по 6 — C и последняя B.

Ввод: s = "AABBBAB"k = 2
Вывод: 6
Пояснение: В ABBBAB с индексами от 1 до 6 две буквы A — единственные буквы, которые не являются B, поэтому две замены дают BBBBBB. Вся строка содержит три A и четыре B, поэтому ей нужны три замены.

+17 скрытых тестов при отправке

Дополнительный вопрос

Что изменится, если s может содержать любой символ, а не только 26 заглавных букв?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Стоимость одной подстроки очевидна: её длина минус количество наиболее часто встречающейся буквы. Сложность в том, чтобы не вычислять стоимость всех n² подстрок. Скользящее окно просматривает строку один раз, а лучший вариант основан на двух фактах: окно никогда не нужно сужать, а максимальное количество вхождений буквы никогда не должно уменьшаться.

Проверьте каждую подстроку

Верно, но не успевает на самых больших тестах

Идея

Исправьте одну подстроку. Какой буквой её следует заменить? Той, которая уже встречается чаще всего, потому что все остальные буквы нужно заменить. Значит, для подстроки длины len, в которой самая частая буква встречается top раз, требуется len - top замен, и она подходит, если это число не превышает k.

Попробуйте все подстроки. Для каждой начальной позиции расширяйте конец на одну букву за раз и ведите подсчёт каждой буквы, по ходу увеличивая top. Тогда для каждой новой подстроки понадобится одно обновление вместо нового подсчёта. Проверяются все подстроки, поэтому самая длинная подходящая подстрока не останется незамеченной.

Это медленно, потому что строка длины n содержит около n²/2 подстрок. Для n = 5 × 10^4 это 1.25 × 10^9 проверок — намного больше, чем позволяет лимит времени.

Алгоритм

Установи best равным 0.
Для каждого начального индекса сбрасывай 26 счетчиков и top до 0.
Перемещай end от начала до последнего индекса. Увеличивай счетчик для s[end] и повышай top, если теперь этот счетчик стал наибольшим.
Если end - start + 1 - top ≤ k, подстрока достижима: сохраняй ее длину, если она больше best.
Верни best.

def characterReplacement(s, k):
    n = len(s)
    best = 0
    for start in range(n):
        count = [0] * 26  # letters in s[start..end]
        top = 0           # count of the most common letter there
        for end in range(start, n):
            c = ord(s[end]) - ord('A')
            count[c] += 1
            top = max(top, count[c])
            # Every letter that is not the most common one must change.
            if end - start + 1 - top <= k:
                best = max(best, end - start + 1)
    return best

Одно скользящее окно на каждую целевую букву

Идея

Измените формулировку задачи и сначала выберите букву. Если итоговая строка состоит только из A, вопрос звучит так: какова самая длинная подстрока, в которой не более k букв, отличных от A? Это классический метод скользящего окна.

Перемещайте right по строке и считайте буквы внутри окна, отличные от целевой. Когда их количество превысит k, передвигайте left вперёд, пока их снова не станет k. Расширение окна может только добавить буквы, которые нужно изменить, поэтому слишком затратное окно останется таким же затратным и после расширения, а left никогда не придётся передвигать назад. Для каждого right сохраняемое окно — самое длинное подходящее окно, заканчивающееся в этой позиции.

Выполните это для всех 26 букв и сохраните наилучшую длину. Каждый проход занимает O(n), поэтому всего будет 26 проходов — примерно 1.3 × 10^6 шагов при n = 5 × 10^4. Это линейная сложность, но строка читается 26 раз, и такой подход работает только потому, что алфавит небольшой.

Алгоритм

Для каждой целевой буквы от A до Z начни с окна, где left = 0 и others = 0.
Перемещай right по строке. Если s[right] не является целевой буквой, увеличь others на единицу.
Пока others > k, перемещай left вперёд и уменьшай others на единицу, если уходящая буква не является целевой.
Сохрани right - left + 1, если это значение больше best.
После обработки всех 26 букв верни best.

def characterReplacement(s, k):
    best = 0
    for target in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
        left = 0
        others = 0  # letters in s[left..right] that are not target
        for right in range(len(s)):
            if s[right] != target:
                others += 1
            # Too many letters to change: drop letters from the left.
            while others > k:
                if s[left] != target:
                    others -= 1
                left += 1
            best = max(best, right - left + 1)
    return best

Окно, которое никогда не уменьшается

Идея

Обрабатывайте каждую букву в одном окне. Поддерживайте в нём счётчик для каждой из 26 букв и top — максимальное количество вхождений. Для окна требуется length - top замен, поэтому оно подходит, если это значение не превышает k.

Первый факт: окну никогда не нужно уменьшаться. Вас интересует только то, чтобы превзойти наибольшую длину, найденную к этому моменту, поэтому, если добавление s[right] делает окно слишком дорогим, удалите одну букву слева. Окно сдвинется на один шаг, сохранив свою длину. Когда окно не слишком дорогое, оно увеличивается на один символ. Поэтому его длина всегда равна наибольшей длине, найденной к этому моменту, а в конце ответ равен n - left.

Второй факт: значение top никогда не нужно уменьшать. Когда буква уходит слева, оставляйте top без изменений, поэтому оно может быть больше фактического количества вхождений внутри окна. Это безопасно. После сдвига длина окна равна ровно top + k, поэтому для его увеличения нужна буква, которая встречается внутри окна top + 1 раз, и в этот момент top увеличивается вместе с ней. Устаревшее значение top может заставить окно сдвинуться, но никогда не приведёт к ошибочному увеличению. Сдвиг ничего не теряет, поскольку рекорд может побить только более длинное окно.

В BAAACAB при k = 1 окно увеличивается до BAAA, а затем для BAAAC нужны 2 замены, поэтому оно сдвигается до AAAC. Добавление следующей A увеличивает top до 4, и окно увеличивается до AAACA длиной 5. Последняя B заставляет его сдвинуться ещё раз, поэтому ответ — 5.

Алгоритм

Поддерживай количество 26, left = 0 и top = 0.
Передвигай right по строке: добавляй s[right] к его количеству и увеличивай top, если это количество теперь больше.
Если right - left + 1 - top > k, окну требуется слишком много изменений: убери s[left] из подсчётов и передвинь left на один шаг. Окно сдвигается и сохраняет свою длину.
Никогда не уменьшай top, когда буква выходит из окна.
Верни длину итогового окна, n - left.

def characterReplacement(s, k):
    count = [0] * 26  # letters inside the window s[left..right]
    left = 0
    top = 0  # the highest count any letter has reached in a window
    for right in range(len(s)):
        c = ord(s[right]) - ord('A')
        count[c] += 1
        top = max(top, count[c])
        # Needs more than k changes: slide the window instead of growing it.
        if right - left + 1 - top > k:
            count[ord(s[left]) - ord('A')] -= 1
            left += 1
    # The window only grew when a longer valid substring was found.
    return len(s) - left

Ловушки и крайние случаи

Код для работы с окном короткий, поэтому большинство неправильных ответов связано с формулой стоимости или с упрощением, которое лишь выглядит правильным.

Прибавление k к длине самой длинной последовательности. В AAAB при k = 3 получится 6 — больше длины строки. В BAAACAB при k = 1 получится 4, но нужное изменение находится в середине и объединяет две последовательности в одну длиной 5.
Подсчёт изменений относительно первой буквы окна вместо самой частой. Для окна BAAA нужна одна замена, а не три.
Возврат n - left в версии, где окно может сужаться. Это упрощение работает только тогда, когда окно никогда не становится короче, как в приведённом здесь коде с одним окном. Если цикл сужает окно с помощью while и пересчитывает настоящее максимальное значение, сохраняйте отдельную переменную best.
Вычисление длины окна как right - left. Обе границы входят в окно, поэтому прибавьте единицу.
Обработка k = 0 как особого случая. Если замен нет, правило для окна и так возвращает длину самой длинной последовательности из одной буквы.

Частые вопросы4

Какова временная сложность задачи замены повторяющегося символа для получения самой длинной подстроки?

Решение с одним окном работает за время O(n), где n — длина s: right проходит по каждой букве один раз, а left перемещается не более одного раза за шаг. Оно использует O(1) дополнительной памяти: 26 счётчиков и несколько целых чисел.

Почему при сдвиге окна не нужно обновлять максимальную частоту?

Окно лишь пытается побить собственный рекорд. После сдвига его длина равна top + k, поэтому для более длинного подходящего окна какая-то буква должна встречаться чаще, чем top раз, и это в любом случае повышает значение top. Слишком большое значение top лишь удерживает окно на прежней длине; оно никогда не заставляет его расти, когда этого не должно происходить.

Чем это отличается от задачи «Самая длинная подстрока без повторяющихся символов»?

Оба алгоритма перемещают оба края по строке, но правила для подходящего окна различаются. Там окно подходит, если ни один символ не повторяется, и его нужно сужать, пока повтор не исчезнет. Здесь окно подходит, если его длина минус количество самой частой буквы не превышает k, что позволяет окну скользить с фиксированной длиной, а не сужаться.

Можно ли решить эту задачу с помощью бинарного поиска?

Да. Если некоторая подстрока длины L достижима, то достижима и любая более короткая подстрока внутри неё, поэтому можно выполнить двоичный поиск по L. Для каждого L сдвигайте окно фиксированной длины и проверяйте, требуется ли в какой-либо позиции не более k изменений. Это O(n log n), что медленнее решения с одним окном, но такой ответ вполне уместен.

Python

def characterReplacement(s, k):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

s = "BAAACAB"
k = 1

Ожидается

Longest Repeating Character Replacement

Функция

Ограничения

Примеры

Подсказки

Решение

Проверьте каждую подстроку

Одно скользящее окно на каждую целевую букву

Окно, которое никогда не уменьшается

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи