> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/stack/decode-string.md).

# Decode String

{% hint style="info" %}
String, Stack Approach
{% endhint %}

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; there are 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 will not be input like `3a` or `2[4]`.

The test cases are generated so that the length of the output will never exceed `105`.

 

**Example 1:**

<pre><code><strong>Input: s = "3[a]2[bc]"
</strong><strong>Output: "aaabcbc"
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "3[a2[c]]"
</strong><strong>Output: "accaccacc"
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: s = "2[abc]3[cd]ef"
</strong><strong>Output: "abcabccdcdcdef"
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= s.length <= 30`
* `s` consists of lowercase English letters, digits, and square brackets `'[]'`.
* `s` is guaranteed to be **a valid** input.
* All the integers in `s` are in the range `[1, 300]`.

### Solutions

This problem is a classic example of a problem that can be solved using a **stack** data structure. Here’s a step-by-step approach:

1. **Initialize an empty stack**: We’ll use this to keep track of the strings we need to repeat and the number of times we need to repeat them.
2. **Iterate over the input string**: We’ll look at each character one by one.
3. **When we encounter a number**, we know that it represents the number of times the following string should be repeated. We push this number onto our stack.
4. **When we encounter an opening bracket ‘\[’**, this indicates the start of the string to be repeated. We push this onto our stack to mark the beginning of this string.
5. **When we encounter a letter**, we add it to the top of our stack (which should always be a string).
6. **When we encounter a closing bracket ‘]’**, this indicates the end of the current repeated string. We pop elements from our stack until we reach an opening bracket, concatenating these letters together to form our repeated string. We then pop the opening bracket and the number preceding it from our stack, and add the repeated string to our stack that many times.
7. **At the end of our input string**, our stack should contain one element: the decoded string. We return this as our result.

This approach works because the stack allows us to handle the nested structure of the input string, ensuring that we always repeat the correct strings the correct number of times. It’s a bit like peeling an onion: we handle the outermost layer first, then the next layer, and so on, until we reach the core.&#x20;

Steps

```csharp

public class Solution {
public string DecodeString(string s) {
    var stack = new Stack<string>();
    stack.Push("");
    
    int num = 0;
    foreach (char c in s) {
        if (char.IsDigit(c)) {
            num = num * 10 + (c - '0');
        } else if (c == '[') {
            stack.Push(num.ToString());
            stack.Push("");
            num = 0;
        } else if (c == ']') {
            string str = stack.Pop();
            int count = Int32.Parse(stack.Pop());
            var sb = new StringBuilder(stack.Pop());
            for (int i = 0; i < count; i++) {
                sb.Append(str);
            }
            stack.Push(sb.ToString());
        } else {
            stack.Push(stack.Pop() + c);
        }
    }
    return stack.Pop();
 }
}

```

> Complexity

* **Time Complexity:** O(1)
* **Auxiliary Space:** O(1)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://docs-57.gitbook.io/data-structure-and-algorithms/problems/stack/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.