Когда дело доходит до проблем, когда запрашиваются подмассивы или подстроки, их подход к грубой силе в основном аналогичен (O (n²), используйте два цикла for для анализа каждого подмассива). Эта задача идентична задаче Наименьший подмассив с заданной суммой, и, следовательно, я должен начать непосредственно с привлекательного решения со скользящим окном.
Эта статья относится к плану подготовки к собеседованию, который вы можете найти здесь.
Теперь давайте начнем с нашего решения.
Описание
Нам дана строка S и число K, и мы должны найти самую длинную подстроку, содержащую не более K различных символов.
Example 1: Input: S = "ababcbcca", K = 2 Output: 5 Explanation: The longest substring with at most 2 distinct characters is "bcbcc" with characters 'b' and 'c'. Example 2: Input: S = abcde, K = 1 Output: 1 Explanation: Since all the characters of the strings are different, the substring length with K distinct characters depends on K itself.
Решение
Думая об этой проблеме, можно увидеть, что мы запрашиваем подмассив, содержащий некоторые свойства; в этом случае он должен содержать не более K различных символов. Это своего рода подсказки, которые должны заставить вас подумать о шаблоне скользящего окна.
Итак, нам нужно окно, которое динамически меняет свой размер. Он расширяется с правой стороны, добавляя новые элементы, и сжимается с левой стороны, если число отдельных символов увеличивается K.
Чтобы сохранить количество различных символов вместе с их частотой, мы можем использовать хеш-таблицу, где мы добавляем в нее новый элемент, расширяя окно и сжимая окно, мы можем уменьшить частоту выхода символа, и если его частота становится равной нулю, мы можем удалить символ из хеш-таблицы.
Всякий раз, когда окно имеет не более K различных символов, мы можем проверить, является ли его размер самым большим, что мы видели, и запомнить его.
Если вы готовитесь к интервью, вам могут понравиться эти две статьи:
Таким образом, алгоритм для самой длинной подстроки с K различными символами может быть:
- Создайте хеш-таблицу для хранения сопоставления между символами и их частотой.
- Вставляйте новые символы из строки, пока в окне не будет K различных символов. Запомните размер окна как ответ (самый длинный, который мы видели до сих пор).
- Затем начните расширять окно справа или, другими словами, сдвигать окно, добавляя новые элементы.
- Если в какой-то момент количество отдельных символов в окне превысит K, мы уменьшим размер окна с правой стороны и уменьшим частоту перемещения символа до тех пор, пока у нас не останется только K различных символов.
- Всякий раз, когда частота символов в хеш-таблице достигает 0, мы удаляем символ.
- После каждого расширения и сжатия мы проверяем, имеет ли текущее окно самый большой размер, который мы видели, и если да, то запоминаем его.
Пример прояснит ситуацию, предположим, что K = 2.
Следующий код написан на Python с соответствующими комментариями. И, если вы хотите c++, читайте здесь.
Код (Питон)
Output: 5
Код (СРР)
Сложность времени и пространства
Время: внешний цикл for выполняется n раз, где n — количество символов в строке, а внутренний цикл while выполняется для каждого символа только один раз, поэтому временная сложность является линейной или O(n) .
Пробел: мы используем словарь, который в любой момент времени может иметь не более (K+1) ключей; следовательно, пространственная сложность пропорциональна K, O(K).
Спасибо за чтение!
P.S.: Если вам нравится этот непрерывный опыт чтения на этой прекрасной платформе Medium.com, подумайте о том, чтобы поддержать авторов этого сообщества, подписавшись на членство ЗДЕСЬ. Это стоит всего 5 долларов США в месяц и помогает всем авторам.
Если вам понравилось то, что вы только что прочитали, мы будем очень признательны за аплодисменты. Вы можете щедро хлопать в ладоши; это показывает мне, насколько вам понравилась эта история. А если не понравилось? Пожалуйста, оставьте комментарий😋!
Вы также можете подписаться на меня ЗДЕСЬ, чтобы получать обновления историй, которые я пишу.
