Longest Substring with At Most K Distinct Characters

Leet Code Link - https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/description/

Complexity - Medium

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

Solution

We can also find the longest valid window with fewer traversals. Unlike the previous fixed-length sliding window solution, this time we can adjust the window length based on the situation. We will still use the counter counter to record the counter of each type of character within the window.

Specifically, if the current window is valid, we can try to expand the window by moving the right boundary one position to the right, right = right + 1. On the other hand, if the current window is invalid, we keep moving the left boundary to the right (equivalent to removing the leftmost character from the window) until the window becomes valid, that is left = left + 1. During this process, we constantly record the longest valid window seen so far.

As shown in the following figure, we keep adjusting the size of the window and recording the maximum size of the valid window.

• Use a hash map counter to record the number of each character in the current window.

• Set left = 0 and max_size = 0, iterate right from 0 to n - 1, at each step right, increment s[right] by 1:

• Increment counter[s[right]] by 1.

• While len(counter) > k, decrement counter[s[left]] by 1. Delete s[left] from counter if counter[s[left] = 0, and increment left by 1.

• Now the window is valid, update the maximum size of valid window as max_size = max(max_size, right - left + 1).

• Return max_size when the iteration ends.

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        HashMap<Character,Integer> set = new HashMap<>();

        int r = 0;int l =0; int longest =Integer.MIN_VALUE;
        while(r<s.length()){
            set.put(s.charAt(r),set.getOrDefault(s.charAt(r),0)+1);

            while(set.size()>k &&l<s.length()){
                if(set.get(s.charAt(l))==1) set.remove(s.charAt(l));
                else set.put(s.charAt(l),set.get(s.charAt(l))-1);
                l++;
            }
            if(set.size()<=k){
                r++;
            }
            longest = Math.max(longest,r-l);

        }
        return longest;
    }
}

Complexity

Time Complexity - O(N)

Space Complexity - O(K)