Skip to content

Sliding Window

Table of Contents

3. Longest Substring Without Repeating Characters

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """Sliding Window: O(n) time, O(min(n, charset)) space.
        Jump the left edge past each repeated character's previous index.
        """
        left = 0
        res = 0
        seen = {}

        for right, ch in enumerate(s):
            if ch in seen and seen[ch] >= left:
                left = seen[ch] + 1
            seen[ch] = right
            res = max(res, right - left + 1)

        return res

    def lengthOfLongestSubstringSet(self, s: str) -> int:
        """Sliding Window Set: O(n) time, O(min(n, charset)) space.
        Shrink until the current character is unique in the window.
        """
        left = 0
        res = 0
        window = set()

        for right, ch in enumerate(s):
            while ch in window:
                window.remove(s[left])
                left += 1
            window.add(ch)
            res = max(res, right - left + 1)

        return res


def test_length_of_longest_substring():
    s = Solution()
    cases = [
        ("abcabcbb", 3),
        ("bbbbb", 1),
        ("pwwkew", 3),
        ("", 0),
        (" ", 1),
        ("abba", 2),
        ("dvdf", 3),
    ]

    for text, expected in cases:
        assert s.lengthOfLongestSubstring(text) == expected
        assert s.lengthOfLongestSubstringSet(text) == expected

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int lengthOfLongestSubstring(string s) {
    int n = s.length();
    int res = 0;
    int left = 0;
    unordered_set<char> window;

    for (int right = 0; right < n; right++) {
        char ch = s[right];

        while (window.find(ch) != window.end()) {
            window.erase(s[left]);
            left++;
        }

        window.insert(ch);
        res = max(res, right - left + 1);
    }
    return (int)res;
}

int main() {
    string s = "abcabcbb";
    cout << lengthOfLongestSubstring(s) << endl;  // 3
    s = "bbbbb";
    cout << lengthOfLongestSubstring(s) << endl;  // 1
    s = "pwwkew";
    cout << lengthOfLongestSubstring(s) << endl;  // 3
    return 0;
}

438. Find All Anagrams in a String

from typing import List


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        """Fixed Sliding Window: O(n + m) time, O(1) space.
        Track 26 lowercase counts for the current window of length len(p).
        """
        if len(p) > len(s):
            return []

        target = [0] * 26
        window = [0] * 26
        for i, ch in enumerate(p):
            target[ord(ch) - ord("a")] += 1
            window[ord(s[i]) - ord("a")] += 1

        res = []
        if window == target:
            res.append(0)

        left = 0
        for right in range(len(p), len(s)):
            window[ord(s[right]) - ord("a")] += 1
            window[ord(s[left]) - ord("a")] -= 1
            left += 1
            if window == target:
                res.append(left)

        return res


def test_find_anagrams():
    s = Solution()
    assert s.findAnagrams("cbaebabacd", "abc") == [0, 6]
    assert s.findAnagrams("abab", "ab") == [0, 1, 2]
    assert s.findAnagrams("af", "be") == []
    assert s.findAnagrams("baa", "aa") == [1]
    assert s.findAnagrams("", "a") == []