Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem statement
2.
Approach
3.
Algorithm
4.
Code:
5.
Time Complexity 
6.
Space Complexity 
7.
Frequently Asked Questions
8.
Key Takeaways
Last Updated: Mar 27, 2024

Print all the Balanced Brackets Strings that can be formed by replacing '?' in string

Author Apoorv
2 upvotes
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Problem statement

You are given with a string 'check' containing characters,'?', '(' and ')' the task is to replace the character '?' either with the opening bracket '(' or the closing bracket ')'. The final goal is to find all those combinations that lead to Balanced Brackets formation.

 

Example 1

Input

check = ‘????’

 

Output

(())

()()

 

Explanation

 

These are a total of 16 possible combinations, out of which only two are balanced brackets string

((((

((()

(()(

(())

()((

()()

())(

()))

)((( 

)(()

)()(

)())

))((

))()

)))(

))))

Approach

Recursion and backtracking can be used to solve the given problem. The approach is to replace every '?' character with ‘)’, then make a recursive call to the next index and backtrack after the recursion call then change it to '(', then make a recursive call to the next index and again backtrack after recursive call after doing both the recursive calls simply backtrack and put the value again as '?'.

Also see, Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm

  • Take the input string from the user and pass the string and 0th index into the function printBalanceBrackets
  • Check the Base case, i.e., if the index has reached to last means the string is completely replaced now; just check if that replaced string is a Balanced Bracket or not. If the string is balanced, Print the string and return it.
  • Check the character at the current index if it is '?' then replace the character first with'),' then further make a recursive call to the next index and backtrack after the recursion call.
  • Then again, replace the character first with '(', then make a recursive call to the next index and backtrack after the recursion call.
  • After doing both, the recursive calls backtrack and again put the char as '?'
  • If the current character is not '?' then simply recur on the next index

 

Code:

#include <bits/stdc++.h>
using namespace std;

// Function to check Balanced Brackets
bool checkBalance(string check)
{

    stack<char> St;

    // Return false if first character is open
    if (check[0] == ')')return false;

    // Iterate in the string to check balanced brackets
    for (int i = 0; i < check.length(); i++) {

        // Push the char in stack if the char is opening bracket
        if (check[i] == '(') St.push('(');

        // If character is a close bracket
        else {

            /*
                If the stack is empty there is no corresponding opening bracket for the
                closing bracket hence return false otherwise simply pop the top most
                element from stack to make a balance
            */
            if(St.size() == 0) return false;
            else St.pop();

        }
    }

    /*
        If no opening bracket then return false else if there are opening brackets
        return false in that case   
    */
    if(St.size() == 0)return true;
    else return false;

}

// Function to print all the balance strings
void printBalanceBrackets(string check, int index)
{

    // Reached at end of string now check if it is balanced
    if (index == check.length()) {

        // Check if the string is balanced then print the balanced string
        if (checkBalance(check)) cout<<check<<endl;
        return;
    }

    if (check[index] == '?') {

        // replace ? with (
        check[index] = '(';

        printBalanceBrackets(check, index + 1);

        // replace ? with )
        check[index] = ')';

        printBalanceBrackets(check, index + 1);

        // backtrack
        check[index] = '?';
    }
    else {

        // If char is not '?' no need to replace
        printBalanceBrackets(check, index + 1);
    }
}

int main()
{

    string check;
    check = "????";

    // Printing Balance brackets after replacement
    printBalanceBrackets(check, 0);

    return 0;
}

 

Output:

(())
()()

 

Time Complexity 

O(N * 2 ^ N)

The time complexity to Print all Balanced Brackets Strings that can be formed by replacing '?' in the string is O(N * 2 ^ N). Since we are doing a recursion call, for every index, we have two options either to put the opening bracket or either to put the closing bracket, so for all the indexes; we have two choices which will lead to 2^N combinations as recursion will explore all the paths. For every combination, we are checking whether the string formed is balanced or not, which has in itself time complexity of O(N). So in total, the time complexity will be O(N*2^N).

Space Complexity 

O(N)

The space complexity to Print all Balanced Brackets Strings that can be formed by replacing '?' in the string is O(N). Since at all the instances when the recursive call reaches to end index, then we check if the string is balanced or not, which leads to the formation of the stack for checking balance parentheses which cost O(N) space complexity.

 

Frequently Asked Questions

 

  1. What is a stack?
    Stack is a data structure that stores elements in LIFO format that is last in first out format and the operations are performed in a particular order to know more about stack refer to this link stack.
     
  2. How is recursion different from backtracking?
    In recursion, the function calls itself until it reaches a base case. We use recursion in backtracking to investigate all of the possibilities until we find the optimal solution to the problem.
     
  3. What is the time complexity to check whether a string is a balanced bracket?
    The time complexity will be O(N), where N is the size of the string. Here we are linearly iterating in the entire string only once.
     
  4. What is the space complexity to check whether a string is a balanced bracket?
    The space complexity will be O(N), where N is the size of the string. Here we are creating a stack to store the characters of string which will cost extra space in the implementation.

 

Key Takeaways

 

In this blog, we discussed the solution to Print all the Balanced Brackets Strings that can be formed by replacing ‘?’ in a string along with the solution we also explored the time and space complexity of the solution.

Check out this article - Balanced Parentheses

Recommended problems -

 

If you want to learn more about Recursion and Backtracking and want to practice some questions which require you to take your basic knowledge on these topics a notch higher, then you can visit our Guided Path for arrays on  Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.

 

 

Previous article
M Coloring Problem
Next article
Maximum length of a string having even frequency of each character formed by concatenation
Live masterclass