JB TAK FODEGA NHI .... TB TK CHODEGA NHI .... (MAANG)

SQP5 Valid Parentheses

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 '()[]{}'.

Notes

Note: Zoom for Better Understanding

Thought Process

Intuition: We have to keep track of previous as well as most recent opening brackets and also keep in mind the sequence, as after opening of the bracket there should be opposite pairs of brackets. Also handle the corner cases like [ ) ( ] where closing bracket occurs first and opening bracket after it, which is an invalid sequence, as well as [ ( ] ) where the most recent opening didn’t get its opposite pair hence it will also not be valid.

So we have to use a data structure that will keep track of first in and last out, hence we will use the stack.

Approch

Whenever we get the opening bracket we will push it into the stack. I.e ‘{‘, ’[’, ’(‘.

Whenever we get the closing bracket we will check if the stack is non-empty or not.

If the stack is empty we will return false, else if it is nonempty then we will check if the topmost element of the stack is the opposite pair of the closing bracket or not.

If it is not the opposite pair of the closing bracket then return false, else move ahead.

After we move out of the string the stack has to be empty if it is non-empty then return it as invalid else it is a valid string.

Code Zone!

Time Complexity:O(N) Linear Iteration
Space Complexity:O(N) O(N) Stack Space.