LeetCode 340: Longest Substring with At Most K Distinct Characters Solution

Master LeetCode problem 340 (Longest Substring with At Most K Distinct Characters), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

340. Longest Substring with At Most K Distinct Characters

Medium

Hash Table String Sliding Window

Problem Explanation

Explanation:

This problem can be solved using a sliding window approach. We can maintain a hashmap to store the frequency of characters in the current window. As we iterate through the string, we expand the window to the right until we have more than K distinct characters. At this point, we shrink the window from the left until we have exactly K distinct characters. We keep track of the maximum length of the substring found so far.

Here are the steps:

Initialize a hashmap to store the frequency of characters and variables to keep track of the start index of the window and the maximum length of substring found so far.
Iterate through the string using two pointers, expand the window to the right, and update the frequency in the hashmap.
When the number of distinct characters exceeds K, shrink the window from the left and update the frequency in the hashmap until we have K distinct characters.
Update the maximum length of substring found so far.
Repeat the process until the end of the string.

Time Complexity: O(N), where N is the length of the input string. Space Complexity: O(K), where K is the number of distinct characters in the input string.

Solution Code

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k == 0) {
            return 0;
        }
        
        Map<Character, Integer> map = new HashMap<>();
        int start = 0, maxLen = 0;
        
        for (int end = 0; end < s.length(); end++) {
            char currentChar = s.charAt(end);
            map.put(currentChar, map.getOrDefault(currentChar, 0) + 1);
            
            while (map.size() > k) {
                char startChar = s.charAt(start);
                map.put(startChar, map.get(startChar) - 1);
                if (map.get(startChar) == 0) {
                    map.remove(startChar);
                }
                start++;
            }
            
            maxLen = Math.max(maxLen, end - start + 1);
        }
        
        return maxLen;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 340 (Longest Substring with At Most K Distinct Characters)?

This page provides optimized solutions for LeetCode problem 340 (Longest Substring with At Most K Distinct Characters) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 340 (Longest Substring with At Most K Distinct Characters)?

The time complexity for LeetCode 340 (Longest Substring with At Most K Distinct Characters) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 340 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 340 in Java, C++, or Python.

Back to LeetCode Solutions