Motivated by my successful solution to the “Longest Substring Without Repeating Characters” problem on Leetcode, I eagerly present the “Sliding Window” technique, a simple yet intriguing method that leverages two pointers to achieve optimal performance.

---

Problem Description

The problem statement is brief and to the point:

Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Since the required output is simply a count, we can employ the following approach:

• HashSet: to determine whether the next character has already appeared
• Right Pointer: shifting point on the right of the string. Right Pointer iterates entire the length of string
• Left Pointer: shifting point on the left of the string. If the Right Pointer met existing char, the Left Pointer would be shifted till that first duplicated position and removed entirely from the HashSet

For example:

s = abcabcbb
s[left:right] = a
s[left:right] = ab
s[left:right] = abc
s[left:right] = bca <= Here, we will remove first 'a' from 'abca'
s[left:right] = cab <= Similarly, 'b' removed from 'bcab'
s[left:right] = abc <= 'c' removed from 'cabc'
s[left:right] = cb <= Here we removed 'ab' from substring 'abcb'
s[left:right] = b <= Here 'cb' removed from 'cbb'

By sliding the window, we can find the length of the longest substring without any duplicate characters, which is 3 for the given input string.

Python code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        left = 0
        result = 0
        for right in range(len(s)):
            while s[right] in charSet:
                charSet.remove(s[left])
                left += 1
                
            charSet.add(s[right])
            result = max(result, right - left + 1)

        return result

The time complexity of this code is O(n), where n is the length of the input string s.

The for loop iterates over each character in the string once, and the while loop inside the for loop may iterate over some of those characters again, but it only does so once for each character, so the total number of iterations of the while loop is at most n. Therefore, the time complexity of the algorithm is O(n + n) = O(n).

The space complexity of this code is also O(n), because in the worst case, the set charSet will contain all characters in the input string, and therefore will take up O(n) space.

Extension

What if the problem requires us to return the longest substring instead of its length? In that case, we could create a new dictionary with the result length as the key and an array of corresponding substrings as the value, since there could be multiple substrings with the same maximum length.