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

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

## Idea

{% hint style="info" %}
Stack + StringBuilder
{% endhint %}

Keep two stack to track most inner layer number and corresponding string

When 0\~9 met, update number to store the new number

When \[ is met, push current number to numStack and push new StringBuilder to stringStack

When ] is met, pop number from numStack, which is the most inner bracket layer number, and pop StringBuilder from stringStack for the corresponding string inside this bracket

If after poping stringStack, stack if not empty, meaning that this is not the most outer layer, update the previous StringBuilder by peek() with current number of current string (after poping c and 2, string stack not empty, so update a to be a+2c=acc)

Else if stack is empty, meaning is the outmost layer, update result string

If lowercase letter is met, peek() to get current string and update by appending current letter

## Code

```java
public String decodeString(String s) {
        Stack<StringBuilder> stringStack = new Stack<>();
        Stack<Integer> numStack = new Stack<>();
        StringBuilder result = new StringBuilder();
        
        int num = 0;
        for(int i =0; i<s.length(); i++){
            if(s.charAt(i)>='0' && s.charAt(i)<='9'){
                num = num*10+s.charAt(i)-'0';
            }
            else if(s.charAt(i)=='['){
                numStack.push(num);
                stringStack.push(new StringBuilder());
                num=0;
            }
            else if(s.charAt(i)==']'){
                int n = numStack.pop();
                StringBuilder str = stringStack.pop();
                StringBuilder strR = stringStack.size()==0?result: stringStack.peek();
                for(int j = 0; j<n; j++){
                    strR.append(str);
                }
            }
            else{
                StringBuilder str = stringStack.size()==0?result: stringStack.peek();
                str.append(s.charAt(i));
            }
        }
        return result.toString();
        
    }
```


---

# 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://yingzehou.gitbook.io/docs/leetcode/string/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.