Consider it as a 2D problem | O(N) time, O(N) space


  • 0
    G
    for(char c : exp.toCharArray()){
          if(c == '('){
            level++;
            continuum = 0;
          }else{
            if(level > 0){
              map.put(level, 0);
              level--;
              continuum += 2;
               if(map.containsKey(level)){
                 continuum += map.get(level);
               }
              map.put(level, continuum);
              if(map.get(level) > maxLength) maxLength = map.get(level);
            }else{
              // refresh the map
              map = new HashMap<>();
            }
          }
        }
    
        return maxLength;
    

    For this one, take a variable 'level' and increment it by 1 each time when you encounter '(' and decrement by 1 when you encounter ')'.

    Now, whenever you decrement the level, if level > 0 then it means you have a valid substring. Store the length of this valid substring at this level in a HashMap/Array.

    Also, if you had encountered this level before, add the length of the valid substring at this level at that time and update the value.

    On successive decrements, take another value 'continuum' and increase it with the respective number of additional string length.

    If, the level becomes less than 0 at any time, the substring before this index can not be merged with any substring after this index. Therefore, check if the length of the valid substring (if any) is greater than the previous stored maximal length.

    Eg.
    Input: ()()(((())()))))()

    3 ->         ()
    2 ->        (  )()
    1 ->       (       )
    0 -> ()()(          )    ()
    -1 ->                  ))
    So, maximal length = 14


Log in to reply
 

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