Balanced Sequence After Replacement
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

Question

Balanced Sequence After Replacement

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

Accepted Answer

Using Recursion

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.

Space Complexity: OtherExplanation:

O(N), where N is the size of the given string.

Extra space is required for the recursion stack which goes upto a maximum depth of O(N). Also, O(N) space is required for the temporary stack. Hence, the overall space complexity is O(N).

Time Complexity: OtherExplanation:

O(2^N * N), where N is the size of the given string.

For every character ‘X’ in the string, we call the recursive function twice (considering ‘X’ as opening and closing bracket). In the worst case, all the characters of the string can be ‘X’. Hence, there would be O(2^N) recursive calls. Also for every recursive call we create a temporary copy of stack which requires O(N) time. Hence, the overall time complexity is O(2^N * N).

For example:

Input format:

Output format:

Note:

Constraints:

Top Veritas Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Veritas Software Developer