Условие задачи

Даны две строки s и t длинами m и n соответственно. Необходимо найти минимальную подстроку s, которая содержит все символы из t (включая повторяющиеся символы). Если такой подстроки не существует, вернуть пустую строку "".

Тестовые примеры будут сгенерированы таким образом, что ответ будет единственным.

Для решения задачи необходимо написать функцию с именем min_window_substring(s: str, t: str) -> str, которая принимает на вход две строки s и t, и возвращает минимальную подстроку, содержащую все символы из t. Если такой подстроки не существует, вернуть пустую строку.

Примеры

Пример 1:

s = "ADOBECODEBANC"
t = "ABC"
assert min_window_substring(s, t) == "BANC"

Объяснение: Минимальная подстрока, содержащая все символы из t, это "BANC".

Пример 2:

s = "ADOBECODEBANC"
t = "Z"
assert min_window_substring(s, t) == ""

Объяснение: В строке s нет символа "Z", поэтому невозможно найти подстроку, содержащую его.

Решение

Для решения задачи будем использовать алгоритм двух указателей (two pointers algorithm). Начальные индексы left и right будут указывать на начало и конец текущей подстроки. Изначально оба индекса будут равны 0.

Далее будем двигать правый индекс right, пока не найдем подстроку, содержащую все символы из t. После того, как найдем такую подстроку, будем двигать левый индекс left, пока подстрока все еще будет содержать все необходимые символы. Запоминаем длину минимальной найденной подстроки и продолжаем поиск, начиная с позиции, следующей за концом текущей подстроки.

Алгоритм закончит свою работу, когда правый индекс достигнет конца строки s.

Пример кода

def min_window_substring(self, s: str, t: str) -> str:
    # Создаем словарь freq, где для каждого символа из t
    # хранится количество его вхождений в t
    freq = {}
    for c in t:
        freq[c] = freq.get(c, 0) + 1

    # Инициализируем левый и правый индексы
    left = right = 0

    # Инициализируем переменную count, которая будет хранить
    # количество символов из t, которые еще осталось найти
    count = len(freq)

    # Инициализируем переменную min_len, которая будет хранить
    # длину минимальной найденной подстроки
    min_len = float('inf')

    # Инициализируем переменную min_substr, которая будет
    # хранить минимальную найденную подстроку
    min_substr = ""

    # Проходим по строке s с помощью правого индекса right
    while right < len(s):
        # Если символ из s входит в t, уменьшаем его счетчик в freq
        if s[right] in freq:
            freq[s[right]] -= 1
            # Если мы нашли все символы из t, уменьшаем счетчик count
            if freq[s[right]] == 0:
                count -= 1

        # Пока мы нашли все символы из t, двигаем левый индекс left
        while count == 0:
            # Если текущая подстрока короче, чем ранее найденная
            # минимальная подстрока, обновляем значение min_len и min_substr
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_substr = s[left:right+1]

            # Если символ из s входит в t, увеличиваем его счетчик в freq
            if s[left] in freq:
                freq[s[left]] += 1
                # Если мы потеряли один из символов, увеличиваем счетчик count
                if freq[s[left]] > 0:
                    count += 1

            # Двигаем левый индекс left
            left += 1

        # Двигаем правый индекс right
        right += 1

    # Возвращаем минимальную найденную подстроку
    return min_substr