# 11.Decode String

Given an encoded string, return its decoded string.

The encoding rule is: `k[encoded_string]`, where the encoded\_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

```
Example 1:
Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:
Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3:
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Example 4:
Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"
```

## Solution: (Using Stack)

The idea is to use **two stacks, one for integers and another for characters.**\
Traverse the string,

1. Whenever we encounter any number, push it into the integer stack and in case of any alphabet (a to z) or open bracket (‘\[‘), push it onto the character stack.
2. Whenever any close bracket (‘]’) is encounter pop the character from the character stack until open bracket (‘\[‘) is not found in the character stack. Also, pop the top element from the integer stack, say n. Now make a string repeating the popped character n number of time. 
3. Now, push all character of the string in the stack.

```cpp
class Solution
{
public:
    string decodeString(string s)
    {
        if (s == "")
        {
            return s;
        }

        stack<int> intStack;
        stack<char> strStack;
        string res = "";
        for (int i = 0; i < s.length(); i++)
        {

            if (s[i] >= '0' && s[i] <= '9')
            {
                int count = 0;
                while(s[i]>='0' && s[i]<='9'){
                    count = count * 10 + (s[i]-48);
                    i++;
                }
                i--;
                intStack.push(count);
            }
            else if (s[i] == ']')
            {

                int count = 1;
                string temp = "";
                if (!intStack.empty())
                {
                    count = intStack.top();
                    intStack.pop();
                }

                while (!strStack.empty() && strStack.top() != '[')
                {
                    temp = strStack.top() + temp;
                    strStack.pop();
                }

                if (!strStack.empty() && strStack.top() == '[')
                {
                    strStack.pop();
                }

                for (int i = 0; i < count; i++)
                {
                    res = res + temp;
                }

                for (int i = 0; i < res.length(); i++)
                {
                    strStack.push(res[i]);
                }
                res = "";
            }
            else
            {
                strStack.push(s[i]);
            }
        }

        while (!strStack.empty())
        {
            res = strStack.top() + res;
            strStack.pop();
        }

        return res;
    }
};
```

**Time Complexity: O(n)**