DEV Community

Akhil
Akhil

Posted on

Valid parentheses, solving a Facebook interview question.

This is one of the most commonly asked screeing questions, Especially if the interview is conducted by Hackerrank, there's a good chance that they will ask this question. I was asked this exact same question 4 times by Hackerrank.

Question : Given a string 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.
An empty string is considered valid.

Eg:

   string = "()[]{}"              //valid
   string = "[{()]}"              //invalid
   string = ""                    //valid
Enter fullscreen mode Exit fullscreen mode

Let's solve this,

At its bare minimum, the question is asking us to find matching opening and closing parentheses. So for :
"(", ")" is the valid closing parentheses
"{", "}" is the valid closing parentheses
"[", "]" is the valid closing parentheses

Or in other words, we can say that the "pairs" cancel out each other, from this we can say that the order matters.

A good data structure that will help us with :
1 > Storing the parentheses and cancel them when the match is found,
2 > Keeping track of parentheses

is Stack. We shall push the opening parentheses on to the stack and pop it when we encounter a closing parenthesis, and that the same time we can check if the closing parenthesis is the valid match for the parentheses being popped.

Implementation - 1

Here we can make a small optimization of checking if the length is even if it's not then obviously the string is not valid.
Converting the above idea into code :

var isValid = function(S) {
    let stack = [];
    if(S == '') return true;
    if(S%2 != 0) return false;
    for(let s of S){
        if(s == '(' || s == '{' || s == '['){
            stack.push(s);
        }else{
            if(stack.length == 0) return false;
            let c = stack.pop();
            if(c == '(' && s != ')'){
                return false;
            }
            if(c == '{' && s != '}'){
                return false;
            }
            if(c == '[' && s != ']'){
                return false;
            }
        }
    }

    if(stack.length != 0) return false;      // for conditions like "{([])}}}" 
    return true;
};
Enter fullscreen mode Exit fullscreen mode

Now this works well, but can we do better? There are a lot of if-else conditions just for checking the "pairs". Let's try to make it more concise.

Implementation - 2

Since the main work of the if conditions are to match the parentheses, we use another data structure, the Hashmaps.

Since a closing parenthesis must match with a corresponding opening parenthesis, we create a mapping between closing and opening parenthesis.

Alt Text

So the algorithm works this way :
1 > Check if the current symbol is in the hashmap, if not the push it on the stack.
2 > If the current symbol is in the hashmap, then pop from the stack and compare it with the value corresponding to hashmap entry.

So if the top of the current symbol is ")" then we pop from the stack, compare the popped value with the value corresponding to ")" in hashmap which is "(", if they arent same then the string is not valid.

The code will make it a lot clear.

var isValid = function(S) {

    if(S == '') return true;
    if(S.length%2 != 0) return false;

    let map = {};
    map[")"] = "(";
    map["}"] = "{";
    map["]"] = "[";

    console.log(map);

    let stack = [];
    for(let s of S){
        if(!map[s]){
            stack.push(s);
        }else{
            if(stack.length == 0) return false;
            let c = stack.pop();
            if(c != map[s]) return false;
        }
    }

    if(stack.length !=0) return false;
    return true;
};
Enter fullscreen mode Exit fullscreen mode

I hope you liked my explanation if you know a better way of solving this problem then please share it with us :)

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/ValidParentheses.js

Discussion (15)

Collapse
namhle profile image
Nam Hoang Le • Edited on

You can check a number is not equal to zero by if (n) {} or check empty string by if (!s) ....
Of course, just use object literal for you map. :)

The last statement should be return !stack.length.

Bonus point: we can solve it shorter by using recursion and String replace method.

Collapse
akhilpokle profile image
Akhil Author

I wrote this way for code readability :)

Collapse
namhle profile image
Nam Hoang Le • Edited on

Yes, that way is better for products. But the boundary between readability and cleaning is not always clear. :)

Thread Thread
akhilpokle profile image
Akhil Author

True that.

Collapse
js_bits_bill profile image
JS Bits with Bill

Also tried the standard for loop approach which actually proved easier to deal with than every:

const isValid = function(s) {

  const pairs = {
    '(': ')',
    '[': ']',
    '{': '}'
  };

  const openParens = [];
  for (let i = 0; i < s.length; i++) {
    const endParen = pairs[s[i]];

    if (endParen) openParens.push(endParen);
    else if (openParens[openParens.length - 1] === s[i]) openParens.pop();
    else return false;
  } 

  return openParens.length ? false : true;
};
Collapse
akhilpokle profile image
Akhil Author

Awesome work man ! keep up !

Collapse
namhle profile image
Nam Hoang Le

It’s me again. Here’s my solution.

function isValid(s) {
    const t = s.replace(/\(\)|\[\]|\{\}/g, "");
    return s == t ? !s : isValid(t);
};
Collapse
akhilpokle profile image
Akhil Author

Test it here: leetcode.com/problems/valid-parent...

As far as I know, the regex will manipulate string and string manipulation is a bit time consuming heavy in javascript.

But smart and concise code though !

Collapse
namhle profile image
Nam Hoang Le • Edited on

It’s true. C/C++ can solve it in almost 0ms.

Collapse
js_bits_bill profile image
JS Bits with Bill • Edited on

I gave this a shot! Similar to yours, my approach was to split the string and track the expected closing parens in a separate array. I used the every method instead of a for...of loop which works nicely with the empty string case.

const isValid = function(str) {

  const pairs = {
    '(': ')',
    '[': ']',
    '{': '}'
  };

  const closingParens = [];
  return [...str].every(validate);

  function validate(char, i, arr) {
    const isLastChar = i === arr.length - 1;

    // If char found in pairs, push closing paren to arr
    if (pairs[char] && !isLastChar) {
      closingParens.push(pairs[char]);
      return true;

    } else {
      // If char has no closing paren, return false
      if (!closingParens.length) return false;

      // Check if current char is last in arr
      const lastCharInArray = closingParens.pop();

      // If last char and unmatched parens, return false
      if (isLastChar && closingParens.length) return false;

      // If pair found, continue
      if (char === lastCharInArray) return true;
    }
  }
};

What do you think?

Collapse
akhilpokle profile image
Akhil Author

For :"{[]}" it returns false.

Try solving it here : leetcode.com/problems/valid-parent...

Collapse
js_bits_bill profile image
JS Bits with Bill

@akhil I updated it to meet that condition!

Collapse
vladflorescu94 profile image
vladflorescu94 • Edited on

I conduct interviews (not at Facebook), I don't ask questions about algorithms, but I wouldn't probably hire someone who writes code like that, especially if it's a mid-senior position, because there are too many bad practices:

  • var shouldn't be used anymore;
  • variables should have more descriptive names and start with a lowercase character;
  • always ===, never ==;
  • static constants should be defined outside functions;
  • renturn stack.length === 0 is cleaner.

I wrote the implementation below and I find it much cleaner.

const CLOSING_BRACKET_BY_MATCH = {
  '(': ')',
  '[': ']',
  '{': '}',
};

const testBrackets = (input) => {
  const stack = [];
  let len = 0;

  if (input.length % 2 !== 0) {
    return false;
  }

  for (const character of input) {
    if ('([{'.indexOf(character) !== -1) {
      stack.push(character);
      len += 1;
    } else {
      const lastCharacterPushed = stack[len - 1];

      if (len === 0 || (CLOSING_BRACKET_BY_MATCH[lastCharacterPushed] !== character)) {
        return false;
      }

      stack.pop();
      len -= 1;
    }
  }

  return len === 0;
};
Enter fullscreen mode Exit fullscreen mode
Collapse
mayankjoshi profile image
mayank joshi

Amazing post. I loved the concept.🥳

Just one thing, try moving this from webdev to #algorithms tag for better reach among algo geeks.

Collapse
akhilpokle profile image
Akhil Author

My bad, it was meant to be #tutorial.

Thanks a lot for reading :)