Accepted Java O(n) solution with explanation


  • 1
      public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s == null) return 0;
            
        int i = 0; // slow pointer
        int j = 0; // fast pointer
        int max = 0;
        
        // use a map to track the char and its count
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        
        while (j < s.length()) {
          char ch = s.charAt(j);
          
          if (map.size() < 2 || map.containsKey(ch)) {
            // less than 2 distinct chars or the char is in the map already
            // put it to the map and update the count
            map.put(ch, map.containsKey(ch) ? map.get(ch) + 1: 1);
            
            // update the max
            max = Math.max(max, ++j - i);
          } else {
            // we keep removing the old chars from the map
            // till we only have one distinct char
            while (map.size() == 2) {
              ch = s.charAt(i++);
              
              if (map.get(ch) > 1)
                map.put(ch, map.get(ch) - 1);
              else
                map.remove(ch);
            }
          }
        }
        
        return max;
      }

  • 0
    W

    How would you prove it is O(n)? There are two while loops in the code.


  • 0

    Hello, when we say O(n), normally it means that the algorithm will take on the order of n operations. e.g. looping through the list once (or a constant number of times such as twice or only looping through half).

    Please take a look at http://stackoverflow.com/questions/1909307/what-does-on-mean


Log in to reply
 

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