Teaching Kids Programming – Longest Substring with 2 Distinct Characters by Sliding Window Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a string s, find the length of the longest substring that contains at most 2 distinct characters.

Constraints
n ≤ 10,000 where n is the length of s.
Example 1
Input
s = “abccb”
Output
4
Explanation
“bccb” is the longest substring with at most 2 distinct characters.

Longest Substring with 2 Distinct Characters by Sliding Window Algorithm

Let’s use a Counter (or dictionary) to keep the counter of the characters within current sliding window. We keep expanding the window to the right if it does not contain more than 2 unique/distinct characters. Otherwise, we shrink the sliding window by moving the left pointer.

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

class Solution:
    def longestSubstringWith2DistinctChararacters(self, s):
        l, r, n = 0, 0, len(s)
        ans = 0
        win = defaultdict(int)
        while r < n:
            win[s[r]] += 1
            while l <= r and len(win.keys()) > 2:
                win[s[l]] -= 1
                if win[s[l]] == 0:
                    del win[s[l]]
                l += 1
            ans = max(ans, r - l + 1)
            r += 1
        return ans

class Solution:
    def longestSubstringWith2DistinctChararacters(self, s):
        l, r, n = 0, 0, len(s)
        ans = 0
        win = defaultdict(int)
        while r < n:
            win[s[r]] += 1
            while l <= r and len(win.keys()) > 2:
                win[s[l]] -= 1
                if win[s[l]] == 0:
                    del win[s[l]]
                l += 1
            ans = max(ans, r - l + 1)
            r += 1
        return ans

The time complexity is O(N). And the space complexity is O(N) as we are using a hash map object. This is better algorithm than bruteforcing all the substrings:

1
2
3
4
5
6
7
8
9
10

class Solution:
    def longestSubstringWith2DistinctChararacters(self, s):
        n = len(s)
        ans = 0
        for i in range(n):
            for j in range(i, n):
                a = s[i:j+1]
                if len(Counter(a).keys()) <= 2:
                    ans = max(ans, j - i + 1)
        return ans

class Solution:
    def longestSubstringWith2DistinctChararacters(self, s):
        n = len(s)
        ans = 0
        for i in range(n):
            for j in range(i, n):
                a = s[i:j+1]
                if len(Counter(a).keys()) <= 2:
                    ans = max(ans, j - i + 1)
        return ans

The bruteforce takes O(N^3) – O(N^2) for trying every substrings, and O(N) for checking if the substring contains at most 2 characters.

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) —