Stack: Given a string with balanced brackets, you need to print the bracket number

Coding Interview Questions

1 min read

Problem Statement:

You are given a sting s, containing bracket and character.

You need to find the bracket number for each bracket in the string.

Example:

Input: "(a(b))"
Output: 1 2 2 1

Solution Explanation:

We use stack to solve this problem.

For opening bracket, increment counter and push into the stack.

For closing bracket, pop the top value and append to the result.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

vector<int> solution(string &str) 
{
    vector<int> res;
    stack<int> st;
    
    int count = 0;
    
    for (int i = 0; i < str.size(); i++) 
    {
        if (str[i] == '(') 
        {
            count++;
            res.push_back(count);
            st.push(count);
        }
        else if (str[i] == ')') 
        {
            res.push_back(st.top());
            st.pop();
        }
    }

    return res;
}

int main() 
{
    string str = "(a(b))";
    vector<int> result = solution(str);
    
    for (int num : result) 
    {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}