340. Longest Substring with At Most K Distinct Characters

四刷 07/2022

Version #2 Array as map + Sliding window

Time O(N)

Space O(256) ~ O(1)

Runtime: 5 ms, faster than 94.80% of Java online submissions for Longest Substring with At Most K Distinct Characters.

Memory Usage: 43.1 MB, less than 75.93% of Java online submissions for Longest Substring with At Most K Distinct Characters.

class Solution {

    public int lengthOfLongestSubstringKDistinct(String s, int k) {

        int[] map = new int[256];

        int count = 0;

        int start = 0;

        int len = 0;

        for (int end = 0; end < s.length(); end++) {

            char c = s.charAt(end);

            if (map[c] == 0) {

                // this is a character that's not in the sliding window

                count++;

            }

            map[c]++;

            while (count > k) {

                c = s.charAt(start);

                map[c]--;

                if (map[c] == 0) { // all occurrence of this character has been removed from the sliding window

                    count--;

                }

                start++;

            }

            len = Math.max(len, end - start + 1);

        }

        return len;

    }

}

一刷

Version #1 TreeMap solution
Time O(Nlogk)

3.71 %
class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        // keep track of the last occurance of char
        // (left, right]
        int max = 0;
        Map<Character, Integer> lastOccurance = new HashMap<>();
        TreeSet<Integer> treeSet = new TreeSet<>();
        int left = -1;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            Integer lastIndex = lastOccurance.getOrDefault(c, right);
            treeSet.remove(lastIndex);
            lastOccurance.put(c, right);
            treeSet.add(right);
            if (treeSet.size() > k) {
                left = treeSet.pollFirst();
            }
            max = Math.max(max, right - left);
        }
        return max;
    }
}


Version #2
"The key idea of the solution is to use two pointers to maintain a "sliding window". 
We use a int array as a hashmap to store all the characters in the window. 
Each time we move forward the "fast" pointer and increase the size of the sliding window until the number of distinct characters in the window is greater than K. 
The next step is to shrink the window by moving forward the "slow" pointer. In order to get the maximum window size, we must move the minimum steps of the slow pointer. 
So each step we move the slow pointer, we need to update the map and reduce the count of the character when our slow pointer walked pass it. Once we found that there's on character's count decreases to zero, we can know that this character is removed from or valid subarray. "
We can always maintain a global max length variable and update it when or sliding window is expanding.

88.55%
Sliding window with two pointers
Time O(n)
public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k <= 0) return 0;
        int[] count = new int[128];
        int slow = 0, fast = 0;
        int curr;
        int maxLength = 0;
        for (fast = 0; fast < s.length(); fast++) {
            curr = s.charAt(fast);
            //a new character
            if (count[curr] == 0) {
                // no quota for new character
                if (k == 0) {
                     while (--count[s.charAt(slow++)] > 0);
                } else k--;
            }
            count[curr]++;
            maxLength = Math.max(maxLength, fast - slow + 1);
        }
        return maxLength;
    }
}

二刷
86.17 %

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k <= 0) return 0;
        int left = 0, right = 0;
        int length = s.length();
        int maxLength = 0;
        int[] count = new int[256];
        //valid range[left, right]
        while (right < length) {
            if (count[s.charAt(right)]++ == 0) k--;
            while (k < 0) {
                if (--count[s.charAt(left++)] == 0) k++;
            }
            maxLength = Math.max(maxLength, right - left + 1);
            right++;
        }
        return maxLength;
    }
}
三刷 HashMap
55.06 %
class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        // Map<char, count>
        // (left, right] valid substring
        // count increase from 0 to 1, k--
        // count decrease from 1 to 0, k++
        if (s == null || s.length() == 0) {
            return 0;
        }
        Map<Character, Integer> counter = new HashMap<>();
        int max = 0;
        int left = -1;
        int right = 0;
        for (right = 0; right < s.length(); right++) {
            int count = counter.getOrDefault(s.charAt(right), 0);
            if (count++ == 0) {
                k--;
            }
            counter.put(s.charAt(right), count);
            while (k < 0 && left < right) {
                left++;
                count = counter.get(s.charAt(left));
                if (--count == 0) {
                    k++;
                }
                counter.put(s.charAt(left), count);
            }
            max = Math.max(max, right - left);
        }
        return max;
    }
}