Share my Java O(n) Sliding Window Solution


  • 0
    F

    Using Sliding Window and hashmap to recording the status of the current substring.
    j is forwarding and not take back, so the time complexity is O(n)

    public int lengthOfLongestSubstringTwoDistinct(String s) {
            if(s == null || s.length() == 0) {
                return 0;
            }
            int longest = 0;
            int j = 0;
            Map<Character, Integer> map = new HashMap<>();
            for(int i = 0; i < s.length(); i++) {
                while(j < s.length() && map.size() <= 2) {
                    if(map.size() == 2 && !map.containsKey(s.charAt(j))) {
                        break;
                    }
                    longest = Math.max(longest, j - i + 1);
                    if(map.containsKey(s.charAt(j))) {
                        map.put(s.charAt(j), map.get(s.charAt(j)) + 1);
                    } else {
                        map.put(s.charAt(j), 1);
                    }
                    j++;
                }
                map.put(s.charAt(i), map.get(s.charAt(i)) - 1);
                if(map.get(s.charAt(i)) == 0) {
                    map.remove(s.charAt(i));
                }
                
            }
            
            return longest;
        }
    

Log in to reply
 

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