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. В обоих окнах длиной шесть букв есть B и C, поэтому в каждом нужно сделать две замены.

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

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

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

Идея

Для каждого начального индекса увеличивай конечный на одну букву за раз, обновляй счётчик для каждой буквы и top, а затем проверяй условие len - top ≤ k. Для каждой новой подстроки требуется одно обновление вместо подсчёта с нуля, и проверяется каждая подстрока, поэтому самая длинная допустимая не будет пропущена.

Строка длины n содержит примерно n²/2 подстрок: 1.25 × 10^9 проверок при n = 5 × 10^4.

Алгоритм

Установите 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 букв и сохрани лучший результат: 26 линейных проходов по строке длиной до 5 × 10^4 букв. Сложность остаётся O(n) только потому, что алфавит небольшой.

Алгоритм

Для каждой целевой буквы от 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 — наибольшего счётчика. Когда добавление s[right] делает окно слишком затратным, убери одну букву слева: окно сдвигается и сохраняет свою длину, поскольку рекорд может побить только более длинное окно. В противном случае оно увеличивается на один символ. Его длина всегда равна лучшей на данный момент, поэтому ответ — n - left.

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

В строке BAAACAB при k = 1 подстрока BAAAC требует 2 замен и сдвигается до AAAC. Следующая A увеличивает top до 4, и окно растёт до AAACA длиной 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, но замена C объединяет две серии в одну длиной 5.
Подсчёт замен относительно первой буквы окна, а не самой частой. Для BAAA нужна одна замена, а не три.
Возврат n - left из цикла, который сужает окно с помощью while и заново вычисляет настоящий максимум. Такое окно становится короче, поэтому храните отдельное значение best.
Вычисление длины окна как right - left. Обе границы входят в окно, поэтому прибавьте единицу.

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

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

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

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

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

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

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

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

Тест #1

Тест #2

Тест #3

Аргументы

s = "BAAACAB"
k = 1

Ожидаемый вывод

Longest Repeating Character Replacement

Функция

Ограничения

Примеры

Подсказки

Решение

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

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

Одно окно, которое никогда не сжимается

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

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

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