Can anyone explain why this is TLE?


  • 0
    M
     public int lengthOfLongestSubstring(String s) {
    
            HashMap<Character, Integer> map = new HashMap<>();
            int start = 0; int end = 0; int max = 0;
            
            while(end < s.toCharArray().length){
                if(map.containsKey(s.charAt(end)) && map.get(s.charAt(end)) >= start){ //duplicate
                    max = Math.max(end-start, max);
                    start = map.remove(s.charAt(end)) + 1;
                }else{
                    max = Math.max(end-start+1, max);
                }
                map.put(s.charAt(end), end);
                end++;
            }
            return max;
        }
    

  • 0
    W

    HashMap.containsKey(Object): It is O(1) in general, however in worst case it is O(n).

    containsValue is O(n), because without the key it doesn't know where it is and the algorithm has to go over all the values stored in the map.

    public boolean containsKey(Object key) {
      352           return getEntry(key) != null;
      353       }
      354   
      355       /**
      356        * Returns the entry associated with the specified key in the
      357        * HashMap.  Returns null if the HashMap contains no mapping
      358        * for the key.
      359        */
      360       final Entry<K,V> getEntry(Object key) {
      361           int hash = (key == null) ? 0 : hash(key.hashCode());
      362           for (Entry<K,V> e = table[indexFor(hash, table.length)];
      363                e != null;
      364                e = e.next) {
      365               Object k;
      366               if (e.hash == hash &&
      367                   ((k = e.key) == key || (key != null && key.equals(k))))
      368                   return e;
      369           }
      370           return null;
      371       }
    
    

    So in some tests cases, it goes TLE because of that.
    I guess, not sure though that you can solve with map.putIfAbsent.

    If the specified key is not already associated with a value (or is mapped to null) associates it with the given value and returns null, else returns the current value
    

    I hope It helps


Log in to reply
 

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