Самая длинная подстрока без повторяющихся символов

Тема: Два указателя, скользящее окно, хеш-таблицы

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

Имеется строка длиной N, состоящая из английских букв, специальных символов и пробелов. мы хотим найти длину подстроки без дубликатов символов.

Подход 1:

Простым наивным решением был бы подход грубой силы, который включает в себя перебор строки во вложенном цикле for.

Давайте рассмотрим три переменные startIndex, endIndex и ответ. Для начального значения startIndex и endIndex указывают на один и тот же индекс 0. Прежде чем запускать внутренний цикл всякий раз, когда мы увеличиваем endIndex, мы должны убедиться, что символ в этом индексе уже не виден в этом интервале между startIndex и endIndex. Это означает, что мы должны отслеживать каждый символ между интервалами. для этого мы можем использовать хэш-таблицы.

Хэш-таблица — это структура данных, которая помогает хранить пары ключ-значение. Доступно несколько методов, таких как set(), get(), has(), delete(),clear(),keys().

Всякий раз, когда мы видим символ во время выполнения цикла endIndex, сначала проверьте, доступен ли он уже в хэш-таблице. Если он недоступен, мы продолжаем выполнять цикл, увеличивая endIndex, если текущий символ уже присутствует в хеш-таблице, что означает, что этот интервал больше не является подстрокой без повторяющихся символов. Мы завершим внутренний цикл и получим значения endIndex.

Теперь нам нужно вычесть startIndex и endIndex, чтобы получить уникальный интервал символов, и сравнить его с ответом, является ли текущий интервал самым большим среди других интервалов, найденных ранее. Если текущий интервал максимальный, мы заменим ответ вычтенным значением между startIndex и endIndex.

Затем мы увеличим startIndex и инициализируем значение endIndex значением startIndex + 1. Кроме того, нам необходимо полностью очистить сохраненные пары ключ-значение в нашей хэш-таблице. Этот процесс будет выполняться до тех пор, пока startIndex не станет меньше длины данной строки.

Как мы видим, это отнимает очень много времени, что приводит к ошибке превышения лимита времени.

Временная и пространственная сложность:

Время: O(N²) где N — длина строки
Пробел: O(N) когда вся строка уникальна без повторяющихся символов

Мы можем добиться большего, чем этот подход.

Подход 2:

Мы можем использовать технику двух указателей, чтобы найти интервал без повторяющихся символов.

Давайте возьмем те же переменные startIndex = 0 и endIndex = 1. Мы по-прежнему будем использовать хеш-таблицу для хранения наших пар ключ-значение. Теперь сохраните символ startIndex в хеш-таблице, ключ — это символ, а значение — его индекс.

Давайте возьмем цикл while, который завершится, когда мы достигнем конца заданной строки.

Сначала мы получим символ строки в позиции endIndex. мы проверим, доступен ли он уже в хеш-таблице.

  • Если символ доступен, мы должны увеличить указатель startIndex до значения индекса + 1, хранящегося в хеш-таблице для этого символа. Это означает, что мы не можем получить неповторяющуюся подстроку, поскольку текущий символ уже доступен в интервале. Кроме того, мы хотим убедиться, что значение индекса, взятое из хеш-таблицы, не перемещает startIndex ниже предыдущего startIndex. Затем мы установим для текущего символа новый доступный endIndex и увеличим endIndex до следующего индекса.
  • Если персонаж недоступен, мы просто сохраним его в хэш-таблице и двинемся дальше.
  • В конце цикла нам нужно сравнить ответ с ранее вычисленными значениями ответа, чтобы получить максимальную длину интервала, доступного в строке.

Когда endIndex превысит длину строки, мы завершим цикл и вернем ответ.

Временная и пространственная сложность:

Время: O(N) где N — длина заданной строки
Пробел: O(N) когда вся строка уникальна без повторяющихся символов

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let map = new Map(), n = s.length, ans = 0;
    
    if(n == 0 || n == 1) {
        return n;
    }

    let startIndex = 0, endIndex = 1;
    map.set(s.charAt(startIndex), 0);

    while(endIndex < n){
        let c = s.charAt(endIndex);
        if(map.has(c)){
            startIndex = Math.max(startIndex, map.get(c) + 1);
            map.set(c, endIndex);
            endIndex++;
        }else{
            map.set(c, endIndex);
            endIndex++;
        }
        ans = Math.max(ans, endIndex - startIndex);
    }
    
    return ans;
};

Вывод:

Таким образом, мы снизили временную сложность с O(N²) до O(N).