My java solution


  • 0
    Z
    import java.util.HashMap;
    import java.util.Map;
    
    public class Solution {
        public int lengthOfLongestSubstringTwoDistinct(String s) {
            Map<Character, Integer> uniqueChars = new HashMap<>();
            int head = 0, tail = 0, length = 0;
    
            while (tail < s.length()) {
                while (uniqueChars.size() < 3 && tail < s.length()) {
                    increment(uniqueChars, s.charAt(tail++));
                }
                length = Math.max(length, tail-head-(uniqueChars.size() > 2 ? 1 : 0));
    
                while (uniqueChars.size() > 2 && head < tail) {
                    decrement(uniqueChars, s.charAt(head++));
                }
                length = Math.max(length, tail-head-1);
            }
    
            return length;
        }
    
        private static void increment(Map<Character, Integer> map, char c) {
            Integer count = map.get(c);
            if (count == null) {
                map.put(c, 1);
            } else {
                map.put(c, count + 1);
            }
        }
    
        private static void decrement(Map<Character, Integer> map, char c) {
            Integer count = map.remove(c);
            if (count > 1) {
                map.put(c, count - 1);
            }
        }
    }
    

    It is O(n) time and O(1) space (even it uses hash map it will contain 3 elements max).


  • 1
    W

    How would you prove it is O(N)? There are two levels of while loops.


  • 0
    Z

    There is a window which consists of the pair head/tail. The outer loop moves this window.

    Also you may notice that the outer loop and the first inner loop share the same variable - tail (and the same condition tail < s.length()).


Log in to reply
 

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