Longest Sliding Window

Use Cases

Use Case	Description	Example
Finding the Longest Substring Without Repeating Characters	Given a string, find the length of the longest substring that contains no repeating characters.	For the string "abcabcbb", the longest substring without repeating characters is "abc", with a length of 3.
Finding the Longest Valid Parentheses	Given a string containing just the characters '(' and ')', find the length of the longest valid parentheses substring.	For the string "(()())", the longest valid parentheses substring is "(()())", with a length of 6.
Finding the Longest Subarray with a Given Sum	Given an array of integers, find the length of the longest contiguous subarray that sums to a specified value.	In the array [1, -1, 5, -2, 3] with a target sum of 3, the longest subarray is [1, -1, 5, -2], with a length of 4.

Code Template

Initializes variables

res will hold the maximum length of the longest valid substring found during the iteration.
left indicates the starting index of the current substring being evaluated.
state creates a dictionary that counts occurrences (default is 0) of each character in the current substring.

Update and check current state

state[s[i]] += 1: This increases the count of the current character s[i] in the state dictionary.
The while loop checks if the current character counts in state form a valid substring (as defined by the valid function). If not valid, it reduces the count of the character at the current left index, effectively "removing" it from the current substring.

Clean up and update result

Remove the character from state if its count is zero.
Update the result with the maximum length of valid substring found

Implement valid() function

Implement valid() based on problem requirements
You can also use while state[s[i]] > 1 to replace while not valid(state, s[i]) function in this simple case.

def longest_valid(s):
    res = 0
    left = 0
    state = defaultdict(int)

Common mistakes

Wrong State Initialization/Update

# Wrong: forgetting to initialize state
state[s[i]] += 1  # KeyError if not using defaultdict
# Wrong: incorrect state cleanup
if state[s[left]] == 0:  # Should remove key when count is 0
    state[s[left]] -= 1  # Creates negative counts
# Correct:
state = defaultdict(int)
state[s[i]] += 1
if state[s[left]] == 0:
    del state[s[left]]

Wrong Window Boundary Update

# Wrong: incorrect window size calculation
res = max(res, i - left)  # Missing +1 for inclusive range
# Wrong: incorrect left pointer movement
left = i  # Skips too many characters
# Correct:
res = max(res, i - left + 1)
left += 1

Issues and consideration

Input Validation: The function does not validate the input type. If s is not a string, the code will raise errors. Adding a check to ensure s is a string would improve robustness.

3. Longest Substring Without Repeating Characters

class Solution:
    def lengthOfLongestSubstring(self, s):
        res = 0
        left = 0
        state = defaultdict(int)
        
        for i in range(len(s)):
            state[s[i]] += 1
            # While the current character is repeating in the window
            while not self.valid(state, s[i]):
                state[s[left]] -= 1
                if state[s[left]] == 0:
                    del state[s[left]]
                left += 1
            res = max(res, i - left + 1)
        return res

    def valid(self, state, char):
        # Check if the current character has more than 1 occurrence
        return False if state[char] > 1 else True

159. Longest Substring with At Most Two Distinct Characters

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s):
        res = 0
        left = 0
        state = defaultdict(int)
        
        for i in range(len(s)):
            state[s[i]] += 1
            while len(state) > 2:
                state[s[left]] -= 1
                if state[s[left]] == 0:
                    del state[s[left]]
                left += 1
                
            res = max(res, i - left + 1)
        return res

340. Longest Substring with At Most K Distinct Characters

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s, k):
        res = 0
        left = 0
        state = defaultdict(int)
        
        for i in range(len(s)):
            state[s[i]] += 1
            while len(state) > k:
                state[s[left]] -= 1
                if state[s[left]] == 0:
                    del state[s[left]]
                left += 1
                
            res = max(res, i - left + 1)
        return res

904. Fruit Into Baskets

class Solution:
    def totalFruit(self, fruits):
        res = 0
        left = 0
        state = defaultdict(int)
        
        for i in range(len(fruits)):
            state[fruits[i]] += 1
            while len(state) > 2:
                state[fruits[left]] -= 1
                if state[fruits[left]] == 0:
                    del state[fruits[left]]
                left += 1
                
            res = max(res, i - left + 1)
        return res

Longest Sliding Window

Use Cases

Code Template

Initializes variables

Update and check current state

Clean up and update result

Implement valid() function

Common mistakes

Issues and consideration

Related Problem

Resources