Напишите функцию, которая по строке вернёт длину самой длинной подстроки без повторяющихся символов.
Вход: "abcabcbb"
Выход: 3 (ответ "abc" — длина 3)
Решение
Оптимальное решение
// «Two Pointers» (два указателя) в своей специфической разновидности — «Sliding Window» (скользящее окно)// Временная сложность: O(n) каждый символ добавляется и удаляется из Set не более одного раза// Пространственная сложность: O(k) для хранения уникальных символов в окнеfunction lengthOfLongestSubstring(s) { let seen = new Set(); let left = 0; let maxLength = 0; // Цикл проходит по строке один раз (указатель right) -> O(n) for (let right = 0; right < s.length; right++) { // Внутренний while может выполняться несколько раз, но суммарно // левый указатель (left) пройдет по строке только один раз за весь алгоритм -> амортизированное O(n) while (seen.has(s[right])) { seen.delete(s[left]); left++; } seen.add(s[right]); maxLength = Math.max(maxLength, right - left + 1); } return maxLength;}
Альтернативное решение (наивный Brute Force, O(n²))
// Временная сложность: O(n^2) (в худшем случае, например, для строки "abcdef").// Пространственная сложность: O(k), где K — размер набора уникальных символов (алфавита).function lengthOfLongestSubstringNaive(s) { let maxLength = 0; // Внешний цикл проходит по каждому символу как началу подстроки -> O(n) for (let i = 0; i < s.length; i++) { let seen = new Set(); let currentLength = 0; // Внутренний цикл строит подстроку от i до конца -> O(n) в худшем случае for (let j = i; j < s.length; j++) { // Проверка наличия в Set -> O(1) if (seen.has(s[j])) { break; // Если символ повторился, прекращаем текущую подстроку } seen.add(s[j]); currentLength++; maxLength = Math.max(maxLength, currentLength); } } // Итоговая сложность: O(n) * O(n) = O(n^2) return maxLength;}