Sliding Window Technique – That Girl Coder

Problem Statement

In a string s, find the length of the longest substring without repeating characters.

Example

Input: s = “abcabcbb”
Output: 3 (“abc”)

Note: Substring means that the letters in the string should be continuous.

Thought Process

The brute force approach to this problem is to construct every possible substring from the given string and keep track of the longest seen substring so far without any repeating characters. This is highly inefficient.

Whenever we want to optimize array or string problems which have some kind of order in them, in this case the continuity of a substring, it’s good to pause and consider whether we can apply the two pointer technique or the sliding window approach. Think about using two pointers in the following situations.

Using two pointers starting at the beginning and end of the array to shrink our search space while comparing the specific elements at start and end pointers
Two pointers starting at the beginning of the array and one moving at a faster speed than the other

Think of sliding window approach in the following situation.

This technique can be used when we need to solve contiguous subarray/ substring problems to solve the overall problem. The window size may be fixed or variable. The window size is variable when we need to find the subarray or the substring in the given problem that meets a certain criteria which is the scenario in this current problem.

Let’s use two pointers called start and end to shrink and expand our sliding window accordingly.

Expand the window when there are no repeated characters in the sliding window
Shrink it when we see a repeated character

Now that we are certain about how we will be using the pointers, the next step is to think about how to formulate shrinking and expansion.

How do we keep track of characters already seen?

As we expand our sliding window considering each additional character added to the substring, let’s store a mapping of a character and the last index where it was seen in a hash map.

lastSeenIndexes = {a: 0, b: 1} etc.

To expand:

We can use the end pointer to traverse the string from left to right for every iteration from i = 0 to i = n-1.

To shrink:

Shrinking the sliding window means determining the position of the start pointer.

The start pointer may have already advanced past the last repeated character
Or we need to move it to the index right after the index of the last seen character

start = max(start, lastSeenIndexes[c] + 1)

Complexity

O(N) time complexity and O(N) space

Solution

def lengthOfLongestSubstring(self, s):
     """
     :type s: str
     :rtype: int
     """
     if not s:
        return 0
        
     start, maxLen = 0, 0
     lastSeenIndexes = {}
        
     for end in range(len(s)):
         c = s[end]
            
         if c in lastSeenIndexes:
             start = max(start, lastSeenIndexes[c] + 1)
                
         lastSeenIndexes[c] = end
            
         maxLen = max(maxLen, end - start + 1)
            
    return maxLen

Hope you enjoyed this step by step problem solving approach for the longest substring without any repeating characters problem!

Category: Sliding Window Technique

Longest Substring Without Repeating Characters

Problem Statement