Skip to content

340. Longest Substring with At Most K Distinct Characters πŸ”’

Description

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

Solutions

Solution 1: Sliding Window + Hash Table

Thinking

Longest substring with at most \(k\) distinct characters. Checking every pair of ends is \(O(n^2)\). Distinctness grows with the right end and shrinks when the left advances, so a sliding window works.

Admit the right character; while the map has more than \(k\) keys, drop the left. The window is always the longest legal suffix of the prefix, and the length is \(n-l\).

We can use the idea of a sliding window, with a hash table \(\textit{cnt}\) to record the occurrence count of each character within the window, and \(\textit{l}\) to denote the left boundary of the window.

Iterate through the string, adding the character at the right boundary to the hash table each time. If the number of distinct characters in the hash table exceeds \(k\), remove the character at the left boundary from the hash table, then update the left boundary \(\textit{l}\).

Finally, return the length of the string minus the length of the left boundary.

The time complexity is \(O(n)\), and the space complexity is \(O(k)\). Here, \(n\) is the length of the string.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        l = 0
        cnt = Counter()
        for c in s:
            cnt[c] += 1
            if len(cnt) > k:
                cnt[s[l]] -= 1
                if cnt[s[l]] == 0:
                    del cnt[s[l]]
                l += 1
        return len(s) - l

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> cnt = new HashMap<>();
        int l = 0;
        char[] cs = s.toCharArray();
        for (char c : cs) {
            cnt.merge(c, 1, Integer::sum);
            if (cnt.size() > k) {
                if (cnt.merge(cs[l], -1, Integer::sum) == 0) {
                    cnt.remove(cs[l]);
                }
                ++l;
            }
        }
        return cs.length - l;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        unordered_map<char, int> cnt;
        int l = 0;
        for (char& c : s) {
            ++cnt[c];
            if (cnt.size() > k) {
                if (--cnt[s[l]] == 0) {
                    cnt.erase(s[l]);
                }
                ++l;
            }
        }
        return s.size() - l;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func lengthOfLongestSubstringKDistinct(s string, k int) int {
    cnt := map[byte]int{}
    l := 0
    for _, c := range s {
        cnt[byte(c)]++
        if len(cnt) > k {
            cnt[s[l]]--
            if cnt[s[l]] == 0 {
                delete(cnt, s[l])
            }
            l++
        }
    }
    return len(s) - l
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function lengthOfLongestSubstringKDistinct(s: string, k: number): number {
    const cnt: Map<string, number> = new Map();
    let l = 0;
    for (const c of s) {
        cnt.set(c, (cnt.get(c) ?? 0) + 1);
        if (cnt.size > k) {
            cnt.set(s[l], cnt.get(s[l])! - 1);
            if (cnt.get(s[l]) === 0) {
                cnt.delete(s[l]);
            }
            l++;
        }
    }
    return s.length - l;
}

Comments