title: How to find validity of a string of parentheses, curly brackets and square brackets?
body: <p>I recently came in contact with this interesting problem. You are given a string containing just the characters <code>'('</code>, <code>')'</code>, <code>'{'</code>, <code>'}'</code>, <code>'['</code> and <code>']'</code>, for example, <code>"[{()}]"</code>, you need to write a function which will check validity of such an input string, function may be like this:
  <br>
   <code>bool isValid(char* s);</code>
  <br>
  these brackets have to close in the correct order, for example <code>"()"</code> and <code>"()[]{}"</code> are all valid but <code>"(]"</code>, <code>"([)]"</code> and <code>"{{{{"</code> are not!</p>
  
  <p>I came out with following O(n) time and O(n) space complexity solution, which works fine:</p>
  
  <ol>
  <li>Maintain a stack of characters.</li>
  <li>Whenever you find opening braces <code>'('</code>, <code>'{'</code> OR <code>'['</code> push it on the stack.</li>
  <li>Whenever you find closing braces <code>')'</code>, <code>'}'</code> OR <code>']'</code> , check if top of stack is corresponding opening bracket, if yes, then pop the stack, else break the loop and return false.</li>
  <li>Repeat steps 2 - 3 until end of the string.</li>
  </ol>
  
  <p>This works, but can we optimize it for space, may be constant extra space, I understand that time complexity cannot be less than O(n) as we have to look at every character.</p>
  
  <p>So my question is can we solve this problem in O(1) space?</p>