> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/stacks-and-queues/decode-string.md).

# 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.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like `3a` or `2[4]`.

**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"
```

```java
class Solution {
    public String decodeString(String s) {
        s = "1[" + s + "]";
        Stack<String> st = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c != ']') {
                if (c >= '0' && c <= '9') {
                    StringBuilder number = new StringBuilder();
                    char t = s.charAt(i);
                    while (t >= '0' && t <= '9') {
                        number.append(t);
                        t = s.charAt(++i);
                    }
                    st.push(number.toString());
                    i--;
                } else
                    st.push(c + "");
            } else {
                StringBuilder str = new StringBuilder();
                while (st.peek().compareTo("[") != 0)
                    str.insert(0, st.pop());
                st.pop();
                int multiply = Integer.parseInt(st.pop());
                StringBuilder temp = new StringBuilder();
                while (multiply-- > 0)
                    temp.append(str);
                st.push(temp.toString());
            }
        }
        return st.pop();
    }
}
```