# 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)**


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://soumyajit4419.gitbook.io/ds-algo/stack-and-queue/applications/9.decode-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.