Last Updated: 19 Nov, 2020

Balanced Sequence After Replacement

Easy

Asked in companies

Solve now

Problem statement

You are given a string of length ‘N’ containing only the following characters: ‘[’, ‘{’, ‘(’, ‘)’, ‘}’, ‘]’. At some places, there is ‘X’ in place of any bracket. Your task is to determine that if you replace all the X’s with appropriate brackets, is it possible to get a valid balanced sequence or not.

For example:

For the given string “[X)](X”, the possible replacement for the first X is ‘(‘ and the second X is ‘)’, which makes the sequence “[()]()”, which is a valid balanced sequence. 

For the given string “[XX{”, there is no possible replacement for X which can make it a valid bracket sequence.

Input format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first and only line of each test case or query contains the string.

Output format:

For each test case, print “Valid” if a balanced sequence is possible, otherwise, print “Invalid”, without quotes in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just return 'True' for valid string and 'False' for an invalid string.

Constraints:

1 <= T <= 10 
1 <= N <= 20 

Time limit: 1 sec

Solve now

Approaches

01 Approach

The idea is to use stack data structure and is pretty much similar to the algorithm where we check if the expression is balanced or not.

We mainly have 3 conditions to fulfil i.e.

Opening bracket.
Closing bracket.
Character ‘X’.

Algorithm:

Initialise a stack, say s.
We traverse the whole string such as,

If all the elements of the string are traversed, return true if the stack is empty. Otherwise, return false.
If we incur an opening bracket like ‘[’, ‘{’ or ‘(’, we push the character into stack.
If we incur a closing bracket like ‘]’, ‘}’ or ‘)’, we need to check for 3 things:
→ If the stack is empty, return false.
→ If the top of the stack is the opening bracket same as the incurred closing bracket, pop from the stack and move forward.
→ If the top of the stack is ‘X’, consider that X as the opening bracket, same as the incurred closing bracket, thus, pop ‘X’ from the stack and move forward.
→ If all the above conditions fail, then, it’s clear that the expression is not balanced. Thus, return false.
Now, if we incur ‘X’, this can either be a closing bracket, or an opening bracket.

First, consider it as an opening bracket and push it into the stack. Call recursively for other elements in the string to check if the string is balanced or not.
If you find the string balanced, you have found your way, return true.
Second, if the above point fails, consider X as a closing bracket and pop the top element from the stack, calling for the rest of the string.

Example:

Let us work on example “X(X)”
Initially, stack s = { }
Let the function definition be isValidHelper(String str, stack s, ele) where ele is the index of the current character on which we are working, initially,ele = 0.

isValidHelper( X(X), {}, 0 ):
str[0] = ‘X’, let us consider it as an opening bracket and push it into the stack.
s = { X }.
We call isValidHelper( X(X), {X}, 1 ).
isValidHelper( X(X), {X}, 1 ):
str[1] = ‘(’, we push it into stack.
s = { X, ( }.
We call isValidHelper( X(X), {X, ( }, 2 ).
isValidHelper( X(X), {X, ( }, 2 ):
str[2] = ‘X’, let us consider it as an opening bracket and push it into the stack.
s= { X, (, X }.
We call isValidHelper( X(X), {X, (, X}, 3 ).
isValidHelper( X(X), {X, (, X}, 3 ):
str[3] = ‘)’, we check for the top of stack which is X, consider it as an opening bracket and pop it from stack.
s = { X, ( }.
We call isValidHelper( X(X), {X, ( }, 4 ).
Now, this is tricky, ele becomes 4 i.e. the string is fully traversed, but, the stack isn’t empty, thus, it returns false.
We go back to point ‘c’ i.e isValidHelper( X(X), {X, ( }, 2 ):
This time, let's consider X as the closing bracket, thus, we pop the top element from stack.
s = { X }
We call isValidHelper( X(X), { X }, 3 ).
isValidHelper( X(X), { X }, 3 ):
str[3] = ‘)’, we check for the top of stack which is X, consider it as an opening bracket and pop it from stack.
s = { }.
We call isValidHelper( X(X), {}, 4 ).
Now, this is tricky, ele becomes 4 i.e. the string is fully traversed and the stack is empty, thus, it returns true.

Solve now