Common Problems

Parentheses

• For any openCount < closeCount => not allowed
• For any valid parentheses string: openCount == closedCount

Parentheses problems usually follow these patterns:

1. Use stack: If there are multiple types of parentheses involved.

   • On encountering an opening bracket -> push to the stack
   • On encountering a closing bracket -> pop from the stack
   • You can also compare the opening bracket being popped with the closing bracket if the brackets are going to be non-uniform.

2. Counting opening and closing parentheses: If there is only a single type of bracket involved.

   • Traversing from start (this will validate cases where number of right brackets are more)
     • Maintain a count every time an opening or closing bracket is found.
     • If open==close at any point -> string till that point is valid
       • Check this at the end to validate the whole string
       • Or check at every point to get a valid substring
     • if left<right at any point -> string till that point is invalid
   • Traversing from end (this will validate cases where number of left brackets are more)
     • Same as above - except the invalid check
     • if left>right -> string invalid