340

340. Longest Substring with At Most K Distinct Characters (Medium)

Given a string s and an integer k, return the length of the longest

substring

of s that contains at most k distinct characters.

 

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: The substring is "aa" with length 2.

 

Constraints:

• 1 <= s.length <= 5 * 104
• 0 <= k <= 50

Companies: Yandex, Amazon, Google

Related Topics:
Hash Table, String, Sliding Window

Similar Questions:

• Longest Substring Without Repeating Characters (Medium)
• Longest Substring with At Most Two Distinct Characters (Medium)
• Longest Repeating Character Replacement (Medium)
• Subarrays with K Different Integers (Hard)
• Max Consecutive Ones III (Medium)
• Maximize the Confusion of an Exam (Medium)

Solution 1. Sliding Window

Check out "C++ Maximum Sliding Window Cheatsheet Template!".

Shrinkable Sliding Window:

// OJ: https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int cnt[128] = {}, distinct = 0, i = 0, j = 0, ans = 0, N = s.size();
        while (j < N) {
            distinct += cnt[s[j++]]++ == 0;
            while (distinct > k) distinct -= --cnt[s[i++]] == 0;
            ans = max(ans, j - i);
        }
        return ans;
    }
};

Non-shrinkable Sliding Window:

// OJ: https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int cnt[128] = {}, distinct = 0, i = 0, j = 0, N = s.size();
        while (j < N) {
            distinct += cnt[s[j++]]++ == 0;
            if (distinct > k) distinct -= --cnt[s[i++]] == 0;
        }
        return j - i;
    }
};

Discuss

https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/discuss/1499842/C%2B%2B-Sliding-Window-(%2B-Cheat-Sheet)