Java-General Method easy understanding- modified based on Longest Substring with At Most 2 Distinct Characters


  • 0
    R
    public class Solution {
         // this is a general method to solve this kind of problem
        public int lengthOfLongestSubstringKDistinct(String s, int k) {
            if(s.length() == 0)
                return 0;
            Map<Character, Integer> map = new HashMap<>();
            int maxLen = 0, left = 0, right = 0;
            
            while(right < s.length()){
                if(map.size() <= k){ // for the problem of  "at most 2 distinct characters", only need to change k to 2
                    char c = s.charAt(right);
                    map.put(c,right);
                    right++;
                }
                
                if(map.size() > k){
                    int leftMost = Integer.MAX_VALUE;
                    for(int idx : map.values()){
                        leftMost = Math.min(leftMost, idx);
                    }
                    
                    map.remove(s.charAt(leftMost));
                    left = leftMost + 1;
                }
                
                maxLen = Math.max(maxLen, right - left);
            }
            return maxLen;
        }
        
    }

Log in to reply
 

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