Balanced Sequence After Replacement

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. 

1. Opening bracket.
2. Closing bracket.
3. Character ‘X’.
    

Algorithm:

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

1. If all the elements of the string are traversed, return true if the stack is empty. Otherwise, return false.
2. If we incur an opening bracket like ‘[’, ‘{’ or ‘(’, we push the character into stack.
3. 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.
4. 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.

1. 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 ). 
    
2. isValidHelper( X(X), {X}, 1 ):
   str[1] = ‘(’, we push it into stack.
   s = { X, ( }.
   We call isValidHelper( X(X), {X, ( }, 2 ).
    
3. 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 ).
    
4. 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 ).
    
5. Now, this is tricky, ele becomes 4 i.e. the string is fully traversed, but, the stack isn’t empty, thus, it returns false. 
    
6. 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 ).
    
7. 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 ).
    
8. Now, this is tricky, ele becomes 4 i.e. the string is fully traversed and the stack is empty, thus, it returns true.

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).

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).