Connect with us

Программирование

Задачи с собеседований: Leetcode — Самая длинная подстрока без повторяющихся символов

Для заданной строки задана строка s, найдите длину самой длинной подстроки без повторяющихся символов.

Опубликовано

/

     
     

Задача

Для заданной строки задана строка s, найдите длину самой длинной подстроки без повторяющихся символов.

Примеры:

Ввод: s = «abcabcbb»
Вывод: 3
Объяснение: самая длинная подстрока без повторения символов это «abc» с длинной 3 символа.

Ввод: s = «bbbbb»
Вывод: 1
Объяснение: самая длинная подстрока «b», 1.

Ввод: s = «pwwkew»
Вывод: 3
Объяснение: строка — «wke», длинна 3.

Ограничения

  • 0 <= s.length <= 5 * 104
  • s состоит из английских букв, цифр, символов и пробелов.

Ссылка

Самая длинная подстрока без повторений на Leetcode: https://leetcode.com/problems/longest-substring-without-repeating-characters/

Самая длинная подстрока без повторений: решение

В решении данной задачи надо использовать алгоритм Скользящего окна. Алгоритм «Скользящее окно» можно представить как просмотр фиксированного фрагмента данных, который движется вдоль всего массива или строки. Представьте себе, что вы смотрите на ряд чисел через окошко фиксированного размера, и это окошко постепенно сдвигается, позволяя вам видеть разные части числового ряда.

Код:

Объяснение:

  1. Словарь charIndexMap: используется для хранения последнего индекса каждого символа.
  2. Переменная start: отслеживает индекс начала текущей подстроки, чтобы избежать повторений.
  3. Перебор строки: мы проходим по каждому символу строки и проверяем, был ли этот символ уже встречен в текущей подстроке.
  4. Если символ встречается, сдвигаем начало подстроки, исключая все символы до предыдущего индекса этого символа.
  5. На каждом шаге вычисляем длину текущей подстроки и обновляем максимальную длину.

Временная сложность этого решения составляет O(n), где n — длина строки s.

Объяснение:

  1. Мы проходим по каждому символу строки один раз, используя цикл for с методом enumerated().
  2. Для каждого символа выполняются операции:
    • Проверка, был ли символ уже в словаре charIndexMap, что занимает O(1) времени.
    • Обновление значения в словаре для текущего символа, что также происходит за O(1) времени.
    • Вычисление текущей длины подстроки и обновление переменной maxLength — все эти операции выполняются за O(1).

Таким образом, каждый символ обрабатывается за O(1) времени, и весь цикл выполняется за O(n).

Такое решение является самым быстрым по времени, но потребляет много памяти:

Задачи с собеседований: Leetcode — Самая длинная подстрока без повторяющихся символов

Для того чтобы минимизировать использование памяти, можно обойтись без использования хеш-таблицы, и вместо этого использовать массив фиксированного размера (если мы предполагаем, что строка состоит только из символов ASCII). Например, для строк, состоящих только из английских букв (всего 26 символов), можно использовать массив фиксированного размера 128 (для всех символов ASCII).

Вот решение, которое использует минимальное количество памяти:

Дополнительно

← Еще задачи с собеседований

← Задачи с собеседований: Leetcode — Наибольший общий префикс

← Как решать задачи на Leetcode

Если вы нашли опечатку - выделите ее и нажмите Ctrl + Enter! Для связи с нами вы можете использовать info@apptractor.ru.
Telegram

Популярное

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: