Skip to content

Sliding Window

Table of Contents

159. Longest Substring with At Most Two Distinct Characters

  • LeetCode | LeetCode CH (Medium)

  • Tags: hash table, string, sliding window

  • Prerequisite: 3. Longest Substring Without Repeating Characters
159. Longest Substring with At Most Two Distinct Characters - Python Solution
from collections import defaultdict


# Sliding Window - Variable
def lengthOfLongestSubstringTwoDistinct(s: str) -> int:
    n = len(s)
    if n <= 2:
        return n

    window = defaultdict(int)
    left, res = 0, 0

    for right in range(n):
        window[s[right]] += 1

        while len(window) > 2:
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1

        res = max(res, right - left + 1)

    return res


s = "ccaabbb"
assert lengthOfLongestSubstringTwoDistinct(s) == 5

340. Longest Substring with At Most K Distinct Characters

340. Longest Substring with At Most K Distinct Characters - Python Solution
from collections import defaultdict


# Sliding Window Variable
def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
    n = len(s)
    if n <= k:
        return n

    window = defaultdict(int)
    left, res = 0, 0

    for right in range(n):
        window[s[right]] += 1
        while len(window) > k:
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1
        res = max(res, right - left + 1)

    return res


s = "eceba"
k = 2
assert lengthOfLongestSubstringKDistinct(s, k) == 3

487. Max Consecutive Ones II

1100. Find K-Length Substrings With No Repeated Characters

Comments