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

Задача

Для заданной строки задана строка 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/

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

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

Код:

func lengthOfLongestSubstring(_ s: String) -> Int {
    // Создаем словарь для хранения символов и их индексов
    var charIndexMap = [Character: Int]()
    // Переменная для хранения длины самой длинной подстроки
    var maxLength = 0
    // Индекс начала текущей подстроки
    var start = 0

    // Пробегаем по каждому символу строки
    for (end, char) in s.enumerated() {
        // Если символ уже встречался, обновляем стартовый индекс подстроки
        if let index = charIndexMap[char], index >= start {
            start = index + 1 // начинаем с индекса следующего за найденным
        }
        
        // Обновляем индекс текущего символа
        charIndexMap[char] = end
        
        // Вычисляем длину текущей подстроки и обновляем максимальную длину
        maxLength = max(maxLength, end - start + 1)
    }

    // Возвращаем максимальную длину подстроки без повторений
    return maxLength
}

Объяснение:

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).

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

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

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

    func lengthOfLongestSubstring(_ s: String) -> Int {
    // Массив для хранения индексов символов (для букв в латинском алфавите)
    var seen = Array(repeating: -1, count: 128) // Предполагаем, что символы ASCII (128 символов)
    
    var maxLength = 0
    var start = 0
    
    // Пробегаем по строке
    for (end, char) in s.enumerated() {
        let index = Int(char.asciiValue ?? 0) // Получаем ASCII-значение символа
        
        // Если символ уже был встречен и его индекс >= начального указателя подстроки
        if seen[index] >= start {
            // Обновляем стартовый индекс, чтобы избежать повторов
            start = seen[index] + 1
        }
        
        // Обновляем индекс текущего символа
        seen[index] = end
        
        // Вычисляем длину текущей подстроки и обновляем максимальную длину
        maxLength = max(maxLength, end - start + 1)
    }
    
    return maxLength
    }

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

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

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

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