Самая длинная подстрока без повторяющихся символов
Тема: Два указателя, скользящее окно, хеш-таблицы
Дана строка 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).