Valid Parentheses is a very interesting algorithm question asked in many interviews including FAANG companies.  

The question for an algorithm is, 


Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.
  • Every close bracket has a corresponding open bracket of the same type.


Example 1:

Input: s = "()"
Output: true


Example 2:

Input: s = "()[]{}"
Output: true


Example 3:

Input: s = "(]"

Output: false


Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.

Let's start with the algorithm,


const validParentheses = function(strs) {
const stack=[];
const pairs={
')':'(',
']':'[',
'}':'{',
}
for(let c of strs){
let open=pairs[c]
if(open){
if(stack.pop() !== open)
{
return false;
}
}
else
{
stack.push(c)
}
}
return stack.length==0
}


Here, we have taken two variables, stack and pairs. The stack is empty array and pairs contains parentheses with key as opposite of opening parentheses values. 

In the for loop we will take each parentheses one by one and storing that in open after findind them in the pairs, if that parentheses is not found then open is null then it goes to else statement which pushes that parentheses in the stack. 

If any parenthese matches with pairs then in stack.pop matches with the open parantheses and if the match is found then it will return false. 



This is the approach which we use to get the correct longest common prefix. I hope you understood the algorithm, if you have any orther way of solveing this then please let us know comment section.