Teaching Kids Programming – Longest Substring Without Repeating Characters – Another Version of 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 – Another Version of Two Pointer / Sliding Window Algorithm

We can use a dictionary aka hash map to remember the last index of a character, and the idea is to shrink the windows (move left pointer to the right) to the last position of the currernt/new character.

This is one variant of the Two Pointer – Sliding Window, see another version: Teaching Kids Programming – Longest Substring Without Repeating Characters (Two Pointer / Sliding Window Algorithm).

Both algorithms take O(N) time and O(N) space. Two pointers Left and Right, move only one direction, and thus the maximum distance combined is 2*N where N is the size of the string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:      
        d = {}
        win = set()
        ans = 0
        r = 0
        n = len(s)
        l = 0
        while r < n:
            x = s[r]
            i = d.get(x, -1) + 1
            while l < i:
                win.remove(s[l])
                l += 1
            d[x] = r
            win.add(x)
            ans = max(ans, len(win))
            r += 1
        return ans

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:      
        d = {}
        win = set()
        ans = 0
        r = 0
        n = len(s)
        l = 0
        while r < n:
            x = s[r]
            i = d.get(x, -1) + 1
            while l < i:
                win.remove(s[l])
                l += 1
            d[x] = r
            win.add(x)
            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) —