Home » Technical Interview Questions » String Interview Questions » Valid Parentheses

Valid Parentheses


In Valid Parentheses problem we have given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
    • ( )
    • [ ]
    • { }
  2. Open brackets must be closed in the correct order.
    • ()][ not valid
    • (){[]} valid
    • [(){}] valid

Example

Input: str = “[]{()()}”

Output: The given string contains valid parentheses.

Algorithm for Valid Parentheses

n: length of string

str: input string

  1. Declare and initialize a stack S.
  2. Run a loop on i from 0 to n.
    1. If str[i] is an opening bracket, then push str[i] in the stack.
    2. If str[i] is a closing bracket, then there are two possibilities:
      • If the top bracket present in the stack is the opening bracket of the same type, then pop top element of the stack.
      • Else, return false.
  3. Return S.empty().

Working Process Step By Step

str = [{}()]

n = 6

Step 1: we get opening bracket [, hence push [ in stack.

Valid Parentheses
Valid Parentheses

Step 2: we get opening bracket {,hence push { in stack.

Valid Parentheses

Step 3: we get a closing bracket } and the top of the stack is {, hence do pop operation on the stack.

Valid Parentheses

 

Step 4: we get opening bracket (, hence push ( in the stack.

Step 5: we get a closing bracket ) and the top of the stack is (, hence do pop operation on the stack.

READ  Scramble String

 

Valid Parentheses
Valid Parentheses

Step 6: we get a closing bracket ] and the top of the stack is [, hence do pop operation on the stack.

Valid Parentheses

Implementation for Valid Parentheses

C++ program for Valid Parentheses

#include<bits/stdc++.h>
using namespace std;
bool isValid(string s) {
    stack<char> bracket;
    for (char& c : s) {
        switch (c) {
            case '(': bracket.push(c); break;
            case '{': bracket.push(c); break;
            case '[': bracket.push(c); break;
            case ')': if (bracket.empty() || bracket.top()!='(') return false; else bracket.pop(); break;
            case '}': if (bracket.empty() || bracket.top()!='{') return false; else bracket.pop(); break;
            case ']': if (bracket.empty() || bracket.top()!='[') return false; else bracket.pop(); break;
            default: ; 
        }
    }
    return bracket.empty() ;
}
int main(){
    string s = "[[]{}]()";
    bool check = isValid(s);
    if(check){
        cout<<"The given string contains valid parentheses.";
    }
    else{
        cout<<"The given string contains invalid parentheses.";
    }
}
The given string contains valid parentheses.

JAVA program for Valid Parentheses

import java.util.*; 
public class Main
{
    public static boolean isValid(String s) {
        Stack<Character> bracket = new Stack<>();
        for (char c : s.toCharArray()) {
             switch (c) {
                case '(': bracket.push(c); break;
                case '{': bracket.push(c); break;
                case '[': bracket.push(c); break;
                case ')': if (bracket.empty() || bracket.peek()!='(') return false; else bracket.pop(); break;
                case '}': if (bracket.empty() || bracket.peek()!='{') return false; else bracket.pop(); break;
                case ']': if (bracket.empty() || bracket.peek()!='[') return false; else bracket.pop(); break;
                default: ; 
            }
        }
        return bracket.isEmpty();
    }
  public static void main(String[] args) {
      String s = "{}[)(]";
      boolean check = isValid(s);
          if(check){
                System.out.println("The given string contains valid parentheses.");
            }
            else{
                System.out.println("The given string contains invalid parentheses.");
            }
  }
}
The given string contains invalid parentheses.

Complexity

Time complexity

O(n)

where n is the length of the given string as we are traversing the given string for once.

The pop(), top() and push() operation in stack takes constant time.

READ  Reverse Bits

Space complexity

O(n)

As we can use an extra space of stack and in the worst case, the size of the stack can be n/2

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup