Teaching Kids Programming – Longest Substring Without Repeating Characters (Two Pointer / Sliding Window Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

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.

Constraints:
0 <= s.length <= 5 * 10^4
s consists of English letters, digits, symbols and spaces.

Longest Substring Without Repeating Characters via Bruteforce Algorithm

We can bruteforce all substrings which is going to take O(N^2) because there are C(n, 1) + C(n, 2) substrings which is .

For each substring, we check if all the characters are unique – which requires O(N) – therefore, this bruteforce algorithms needs O(N^3) overall time complexity. The space complexity is O(1) constant.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:      
        n = len(s)
        ans = 0
        
        def check(a):
            return len(a) == len(set(a))
        
        for i in range(n):
            for j in range(i, n):
                if check(s[i:j+1]):
                    ans = max(ans, j - i + 1)
        return ans

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:      
        n = len(s)
        ans = 0
        
        def check(a):
            return len(a) == len(set(a))
        
        for i in range(n):
            for j in range(i, n):
                if check(s[i:j+1]):
                    ans = max(ans, j - i + 1)
        return ans

Longest Substring Without Repeating Characters via Two Pointer / Sliding Window Algorithm

We can keep tracking a current window, and use two pointer to apply the sliding window algorithms. We can expand the window to the right greedily as long as the character is not existent in the current window. Otherwise, we need to move the left pointer and erase the corresponding characters at left pointer out of the window until the current character at the right pointer is no longer in the window.

If we don’t move the left pointer (shrink the window), the substring is not valid no matter how we move the right pointer.

The time complexity is O(N) as the left and right pointers both move towards the right – and the space complexity is O(N) as we need a hash set to store the elements in the current window.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:              
        n = len(s)
        ans = 0
        win = set()
        L = R = 0
        while R < n:
            while s[R] in win:
                win.remove(s[L])
                L += 1
            win.add(s[R])
            ans = max(ans, len(win))
            R += 1
        return ans

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:              
        n = len(s)
        ans = 0
        win = set()
        L = R = 0
        while R < n:
            while s[R] in win:
                win.remove(s[L])
                L += 1
            win.add(s[R])
            ans = max(ans, len(win))
            R += 1
        return ans

Longest Substring Algorithms

• Teaching Kids Programming – Longest Substring Without Repeating Characters – Another Version of Two Pointer / Sliding Window Algorithm
• Teaching Kids Programming – Divide and Conquer Algorithm to Find Longest Substring with Character Count of at Least K
• Teaching Kids Programming – Longest Substring with 2 Distinct Characters by Sliding Window Algorithm
• Compute Longest Substring with At Least K Repeating Characters via Divide and Conquer Algorithm
• Two Pointer Sliding Window to Compute the Longest Substring with At Most Two Distinct Characters
• Two Pointer with Sliding Window Algorithm to Compute the Longest Substring with At Most K Distinct Characters

–EOF (The Ultimate Computing & Technology Blog) —