Share my O(n) java Solution, Extension to K character Avaible


  • 0
    X

    If you need to extend to k characters, replace "2" with "k" in "while(num > 2) {"
    The idea it simply keep track of the following items:

    1. occurrence of each character within the current substring using a hashmap, mem
    2. so far, the length of the longest substring with at most 2 characters, result
    3. how many different characters in the current substring, num
    4. the index of the leftmost character of the following substring, left

    Within the main loop, for each iteration, follow these steps:

    1. add a new character, update mem and num
    2. if the substring has more than 2 characters, (num > 2)
      (1). move left
      (2). update mem, num accordingly
    3. calculate the length of the current substring, update result if necessary

    ...
    public int lengthOfLongestSubstringTwoDistinct(String s) {
    Map<Character, Integer> mem = new HashMap<Character, Integer>();

        int result = 0;
        int num = 0;
        int left = 0;
        
        for(int i = 0; i < s.length(); i++) {
            char curr = s.charAt(i);
            if (!mem.containsKey(curr)) {
                mem.put(curr, 0);
                num++;
            }
            mem.put(curr, mem.get(curr) + 1);
            
            while(num > 2) {
                char leftChar = s.charAt(left);
                mem.put(leftChar, mem.get(leftChar) - 1);
                if (mem.get(leftChar) == 0) {
                    mem.remove(leftChar);
                    num--;
                }
                left++;
            }
            
            result = Math.max(result, i - left + 1);
        }
        
        return result;
    }
    

    ...


Log in to reply
 

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