Two Pointer with Sliding Window Algorithm to Compute the Longest Substring with At Most K Distinct Characters

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

Example 1:
Input: s = “eceba”, k = 2
Output: 3
Explanation: T is “ece” which its length is 3.

Example 2:
Input: s = “aa”, k = 1
Output: 2
Explanation: T is “aa” which its length is 2.

Two Pointer Algorithm with Sliding Window to Compute the Longest Substring with A Most K Distinct Characters

The longest substring is zero empty string for empty string or the K is zero. Then we would have a hash set to record the number of occurences for the characters in the sliding window defined by two pointers.

Each iteration, we extend the current window one position to the right. And we compute the current window size if the number of the unique characters is less or equal to K. And if it is more than K, we need to shrink the window size by moving the left pointer .

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

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int n = s.size();
        if (n == 0 || k == 0) return 0;
        int left = 0;
        unordered_map<char, int> data;
        int maxLen = 1;
        for (int i = 0; i < n; ++ i) {
            data[s[i]] ++;
            if (data.size() <= k) {
                maxLen = max(maxLen, i - left + 1);
            }
            while (data.size() > k) {
                if (--data[s[left]] == 0) {
                    data.erase(s[left]);
                }
                left ++;                
            }
        }        
        return maxLen;
    }
};

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int n = s.size();
        if (n == 0 || k == 0) return 0;
        int left = 0;
        unordered_map<char, int> data;
        int maxLen = 1;
        for (int i = 0; i < n; ++ i) {
            data[s[i]] ++;
            if (data.size() <= k) {
                maxLen = max(maxLen, i - left + 1);
            }
            while (data.size() > k) {
                if (--data[s[left]] == 0) {
                    data.erase(s[left]);
                }
                left ++;                
            }
        }        
        return maxLen;
    }
};

The time complexity is O(NK) and O(N) in the best case. The space complexity is O(K) as we are using a hash set to store the characters frequencies in the K-size window.

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