Given an encoded string, decode string

Problem Statement:

You are given an encoded string, you need to decode it.

Example

Input: s = “3[a]2[bc]”
Output: “aaabcbc”

Solution

To solve this problem, we will use 2 stacks.

One stack will hold the number

Another stack will hold the letters

If we have a string “3[a]2[bc]”

Initially the digit will be put into num stack.
Then we encounter “[“, then we will push the chars in str_stack till we encounter “]”.
num_Stack = 3
str_stack = a

Then when we reach “]”, then we will repeat the string n number of times and then pop both of them.

result = “aaa”

Then 2[bc], we follow the same procedure.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <queue> 
#include <list> 

using namespace std;

string decode_string(string s) 
{
    stack<string> chars;
    stack<int> nums;
    string res;
    int num = 0;
    for(char c : s) 
    {
        if(isdigit(c)) {
            num = num*10 + (c-'0');  // coverts the string number to integer
          //To handle cases like 22[a], this is just using increasing the place value by one and then adding the single digit to the ones place value
                            
        }
        else if(isalpha(c)) {
            res.push_back(c);                
        }
        else if(c == '[') {
            chars.push(res);
            nums.push(num);
            res = "";
            num = 0;
        }
        else if(c == ']') {
            string tmp = res;
            for(int i = 0; i < nums.top()-1; ++i) {
                res += tmp;
            }
            res = chars.top() + res;
            chars.pop(); nums.pop();
        }
    }
    return res;
}

int main()
{ 
  string str = "3[a]2[bc]";
  cout<<"The decoded string is " <<decode_string(str)<<endl;
}

Output:

The decoded string is aaabcbc