LeetCode Top Interview Questions 340. Longest Substring with At Most K Distinct Characters (Java版;

朴灿烈づ我的快乐病毒、 2023-07-04 04:38 17阅读 0赞

### [welcome to my blog][] ###

## LeetCode Top Interview Questions 340. Longest Substring with At Most K Distinct Characters (Java版; Hard) ##

#### 题目描述 ####

Given a string, find the length of the longest substring T that contains at most k distinct characters.
    
    Example 1:
    
    Input: s = "eceba", k = 2
    Output: 3
    Explanation: T is "ece" which its length is 3.
    Example 2:
    
    Input: s = "aa", k = 1
    Output: 2
    Explanation: T is "aa" which its length is 2.

#### 第一次做; 跟下面的方法一样, 就是把res换了个位置 ####

class Solution { 
        public int lengthOfLongestSubstringKDistinct(String s, int k) { 
            if(s==null || s.length()==0 || k==0)
                return 0;
            int left=0, right=0, n=s.length();
            int res = 0;
            HashMap<Character, Integer> map = new HashMap<>();
            //滑动窗口, 双层循环; 外循环中右移right,直至满足条件; 满足条件时, 内循环中右移left,直至不满足条件; 然后重新右移right
            //外循环中右移right
            while(right<n){ 
                char ch = s.charAt(right);
                map.put(ch, map.getOrDefault(ch,0)+1);
                //内循环中右移left, 缩小滑窗
                while(map.size()>k){ 
                    char ch2 = s.charAt(left);
                    map.put(ch2, map.get(ch2)-1);
                    if(map.get(ch2)==0)
                        map.remove(ch2);
                    left++;
                }
                //换位置之后的res
                res = Math.max(res, right - left + 1);
                right++;
            }
            return res;
        }
    }

#### 第一次做; 滑动窗口, 核心:right往右不断扩大窗口到满足(超过)条件, 满足条件时, 内循环中,left不断往右缩小窗口, 直到不满足条件; 不满足条件时继续向右移动right; 细节: res只有在满足条件时才更新, 并且res取历次中的最大值 ####

class Solution { 
        public int lengthOfLongestSubstringKDistinct(String s, int k) { 
            if(s==null || s.length()==0 || k==0)
                return 0;
            int left=0, right=0, n=s.length();
            int res = 0;
            HashMap<Character, Integer> map = new HashMap<>();
            //滑动窗口, 双层循环; 外循环中右移right,直至满足条件; 满足条件时, 内循环中右移left,直至不满足条件; 然后重新右移right
            //外循环中右移right
            while(right<n){ 
                char ch = s.charAt(right);
                map.put(ch, map.getOrDefault(ch,0)+1);
                if(map.size()<=k)
                    //细节
                    res = Math.max(res, right - left + 1);
                //内循环中右移left, 缩小滑窗
                while(map.size()>k){ 
                    char ch2 = s.charAt(left);
                    map.put(ch2, map.get(ch2)-1);
                    if(map.get(ch2)==0)
                        map.remove(ch2);
                    left++;
                }
                right++;
            }
            return res;
        }
    }

#### [力扣优秀题解][Link 1] ####

class Solution:
        def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
            res = 0
            left = 0
            queue = { }
            for right in range(len(s)):
                queue.setdefault(s[right], 0)
                queue[s[right]] += 1
                while len(queue) > k:
                    queue[s[left]] -= 1
                    if queue[s[left]] == 0:
                        queue.pop(s[left])
                    left += 1
                res = max(res, right - left + 1)
            return res

[welcome to my blog]: https://littlehaes.com
[Link 1]: https://leetcode-cn.com/problems/longest-substring-with-at-most-k-distinct-characters/solution/hua-dong-chuang-kou-by-powcai-4/