3. Longest Substring Without Repeating Characters

Задача

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

Примеры

Пример 1

Input: s = "abcabcbb"
Output: 3

Пояснение

Ответ — “abc”, длина 3. “bca” и “cab” тоже верны.

Пример 2

Input: s = "bbbbb"
Output: 1

Пояснение

Ответ — “b”, длина 1.

Пример 3

Input: s = "pwwkew"
Output: 3

Пояснение

Ответ — “wke”, длина 3. Ответ должен быть подстрокой; “pwke” — подпоследовательность, а не подстрока.

Решение

Решение

/**
 * Сложность по времени (Time Complexity): O(n)
 *   В худшем случае каждый символ строки будет посещен дважды: один раз правым указателем (right)
 *   при добавлении и один раз левым указателем (left) при удалении. Поскольку n — это количество
 *   символов в строке, и количество операций линейно зависит от n, сложность составляет O(n).
 *
 * Сложность по памяти (Space Complexity): O(min(n, m))
 *   Мы используем Set для хранения уникальных символов в текущем окне.
 *   В худшем случае (если все символы уникальны) размер Set будет равен длине строки n.
 *   Однако, размер Set также ограничен размером алфавита m (например, 26 для английских букв
 *   или 128 для ASCII). Поэтому сложность O(min(n, m)).
 */
var lengthOfLongestSubstring = function(s) {
    let left = 0;
    let right = 0;
 
    let longest = 0;
    let seen = new Set();
 
    while (right < s.length) {
        const char = s[right];
 
        // Сужаем окно слева, пока не удалим повторяющийся символ
        while (seen.has(char)) {
            seen.delete(s[left]);
            left++;
        }
 
        seen.add(char);
        // Размер Set и есть текущая длина уникального окна (right - left + 1)
        longest = Math.max(longest, seen.size);
        right++;
    }
 
    return longest;
};