Java Solution using maximum sliding window logic


  • 0
    C
        // idea is to implement maximum sliding window logic
        public int lengthOfLongestSubstringKDistinct(String s, int k) {
            Map<Character, Integer> charMap = new HashMap<Character, Integer>();
            int beg = 0, end = s.length() - 1, cur = beg, maxLength = 0;        
            
            while(cur <= end){
                // expanding the window size
                while(cur <= end && charMap.size() <= k){
                    char ch = s.charAt(cur++);
                    charMap.computeIfPresent(ch, (u,v)->v+1);
                    charMap.computeIfAbsent(ch, v -> 1);
                }
                
                // window is invalid so need to remove the last character
                if(charMap.size() > k){
                    maxLength = Math.max(maxLength, cur - beg - 1);
                }
                // window is valid so the last character can be considered
                else{
                    maxLength = Math.max(maxLength, cur - beg);
                }
                
                // shrinking the window size
                while(charMap.size() > k){
                    char ch = s.charAt(beg++);
                    charMap.put(ch, charMap.get(ch) - 1);
                    
                    if(charMap.get(ch) == 0){
                        charMap.remove(ch);
                    }
                }
            }
            
            return maxLength;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.