Longest Substring With At Most K Distinct Characters - Leetcode Solution

Problem Statement:

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.

Approach:

This problem can be easily solved using a sliding window approach. We can use two pointers l and r to represent the left and right end of the current substring. We also use a hashmap to store the frequency of each character in the substring. The key of the hashmap is the character and the value is the frequency.

We start by setting l=0 and r=0. We then move the right pointer r to the right until the substring contains at most k distinct characters. When we add a new character to the substring, we increment its frequency in the hashmap. If the hashmap size becomes greater than k, it means that we have more than k distinct characters in the substring. In this case, we move the left pointer l to the right while decreasing the frequency of the character at position l in the hashmap. We repeat this process until the hashmap size becomes equal to k again.

At each step, we update the maximum length of the substring as r-l+1. The final answer is the maximum length of the substring we have encountered so far.

Algorithm:

1. Initialize l=0, r=0 and a hashmap freq to store the frequency of characters in the current substring.
2. Initialize max_len=0 to store the maximum length of the substring.
3. While r < length(s): a. Increment the frequency of s[r] in the hashmap freq. b. If the size of the hashmap freq > k, move the left pointer l to the right while decreasing the frequency of s[l] in the hashmap freq. This ensures that we have at most k distinct characters in the substring. c. Update max_len=r-l+1. d. Move the right pointer r to the right.
4. Return max_len.

Code:

Here is the python code that implements the above algorithm.

class Solution: def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int: if k == 0 or len(s) == 0: return 0

    l, r = 0, 0
    freq = {}
    max_len = 0
    
    while r < len(s):
        freq[s[r]] = freq.get(s[r], 0) + 1
        
        while len(freq) > k:
            freq[s[l]] -= 1
            if freq[s[l]] == 0:
                del freq[s[l]]
            l += 1
            
        max_len = max(max_len, r-l+1)
        r += 1
        
    return max_len

Time Complexity:

The time complexity of this algorithm is O(n), where n is the length of the input string s. This is because each character is visited at most twice, once by the right pointer and once by the left pointer. The space complexity of this algorithm is O(k), where k is the size of the hashmap freq.

1