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.

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)