# Decode String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/decode-string)
Canonical: https://scaleengineer.com/dsa/problems/decode-string
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Data structures:** String, Stack
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [ByteDance](https://scaleengineer.com/companies/bytedance), [Cisco](https://scaleengineer.com/companies/cisco), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Huawei](https://scaleengineer.com/companies/huawei), [Intuit](https://scaleengineer.com/companies/intuit), [Nutanix](https://scaleengineer.com/companies/nutanix), [Ozon](https://scaleengineer.com/companies/ozon), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Yelp](https://scaleengineer.com/companies/yelp), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [Coupang](https://scaleengineer.com/companies/coupang), [Salesforce](https://scaleengineer.com/companies/salesforce), [razorpay](https://scaleengineer.com/companies/razorpay), [Geico](https://scaleengineer.com/companies/geico), [Flexport](https://scaleengineer.com/companies/flexport), [Splunk](https://scaleengineer.com/companies/splunk), [Tencent](https://scaleengineer.com/companies/tencent), [Roku](https://scaleengineer.com/companies/roku), [Sumo Logic](https://scaleengineer.com/companies/sumo-logic), [Compass](https://scaleengineer.com/companies/compass), [Tesco](https://scaleengineer.com/companies/tesco), [Ola Cabs](https://scaleengineer.com/companies/ola-cabs), [Activision](https://scaleengineer.com/companies/activision), [Hertz](https://scaleengineer.com/companies/hertz), [Mountblue](https://scaleengineer.com/companies/mountblue)
---
## Problem
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:**

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

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

# Approaches
## Brute-Force with String Replacement
This approach repeatedly finds the innermost `k[encoded_string]` pattern, decodes it, and replaces it in the string. This process continues until no encoded patterns are left. It's a straightforward idea but suffers from poor performance due to expensive string operations in a loop.
**Time:** O(N * M) or worse, where N is the number of bracket pairs and M is the length of the output string. In each step, we scan the string (which can grow up to length M) to find brackets. String concatenations and replacements are also expensive. · **Space:** O(M), where M is the length of the output string. A new string of length up to M can be created in each iteration.
**Pros:** Conceptually simple to understand.
**Cons:** Very inefficient due to repeated string scanning and manipulation.; Creating new string objects in a loop is memory and time-intensive in languages like Java.; Will likely result in a 'Time Limit Exceeded' error for larger inputs.
### Explanation
The algorithm iterates as long as there are square brackets `[` in the string. In each iteration, it locates the innermost pair of brackets. This can be done by finding the last occurrence of `[` and the first occurrence of `]` after it. Once the innermost `encoded_string` is identified, the corresponding repeat count `k` is parsed from the digits just before the `[`. The `encoded_string` is repeated `k` times to get the decoded part. Finally, the entire `k[encoded_string]` substring is replaced with the newly decoded part in the main string. This loop continues until the string is fully decoded.

```java
class Solution {
    public String decodeString(String s) {
        while (s.indexOf('[') != -1) {
            int right = s.indexOf(']');
            int left = s.lastIndexOf('[', right);
            
            String encoded = s.substring(left + 1, right);
            
            int k_start = left - 1;
            while (k_start >= 0 && Character.isDigit(s.charAt(k_start))) {
                k_start--;
            }
            k_start++;
            
            int k = Integer.parseInt(s.substring(k_start, left));
            
            StringBuilder decoded = new StringBuilder();
            for (int i = 0; i < k; i++) {
                decoded.append(encoded);
            }
            
            s = s.substring(0, k_start) + decoded.toString() + s.substring(right + 1);
        }
        return s;
    }
}
```
### Algorithm
- Start a loop that continues as long as the string `s` contains the character `[`.
- Inside the loop, find the index of the first `]` character, let's call it `right`.
- Find the index of the last `[` character that appears before `right`, let's call it `left`. This ensures we are processing the innermost bracketed expression first.
- Extract the `encoded_string` which is the substring between `left + 1` and `right`.
- Find the start of the number `k` by scanning backwards from `left - 1` as long as the characters are digits.
- Parse this number `k`.
- Create the decoded part by repeating the `encoded_string` `k` times.
- Construct a new string by replacing the `k[encoded_string]` part with the decoded part.
- Repeat the loop with the modified string.
- Once the loop finishes, return the fully decoded string.

## Recursive Approach (Depth-First Traversal)
This approach treats the string as a nested structure and uses recursion to decode it. A global index is used to keep track of the current position in the string, simulating a parser that consumes the string as it goes. This is a form of depth-first traversal of the encoded structure.
**Time:** O(M), where M is the length of the decoded output string. We traverse each character of the input string once, and the string building operations take time proportional to the final length. · **Space:** O(M), where M is the length of the output string. The recursion call stack depth is at most the nesting level D, but the space for the result `StringBuilder` in each call contributes. The total space for all `StringBuilder`s at any point is bounded by O(M).
**Pros:** Elegant and naturally models the problem's recursive structure.; Efficient in terms of time complexity.
**Cons:** Can lead to stack overflow for extremely deep nesting (though not an issue for the given constraints).; Managing state (the index `i`) via a global or shared variable can sometimes be less clean than passing it explicitly.
### Explanation
The core of this approach is a recursive function that decodes a part of the string and returns the result. We use a global or class-level variable `i` to maintain the current parsing position across recursive calls. The function iterates through the string starting from the current position `i`. If it encounters a letter, it appends it to the result for the current level. If it encounters a digit, it parses the complete number to get the repetition count `k`. When `[` is found, it means a new nested level begins. We make a recursive call to decode the content within the brackets. The result of the recursive call is then appended `k` times to the current level's result. When `]` is found, it signifies the end of the current decoding scope, and the function returns the accumulated string for its level.

```java
class Solution {
    private int i = 0;

    public String decodeString(String s) {
        StringBuilder result = new StringBuilder();
        int count = 0;

        while (i < s.length()) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                count = count * 10 + (c - '0');
                i++;
            } else if (c == '[') {
                i++; // Move past '['
                String decodedSubstring = decodeString(s); // Recursive call
                for (int j = 0; j < count; j++) {
                    result.append(decodedSubstring);
                }
                count = 0; // Reset count for the next number
            } else if (c == ']') {
                i++; // Move past ']'
                return result.toString(); // End of current scope
            } else { // It's a letter
                result.append(c);
                i++;
            }
        }
        return result.toString();
    }
}
```
### Algorithm
- Define a recursive function, say `decode()`, which will parse the string `s`. Use a global index `i` to track the position.
- Initialize an empty `StringBuilder` `result` and a `count` to 0.
- Loop while `i` is within the bounds of `s` and the character is not `]`.
- If `s.charAt(i)` is a digit, update `count`.
- If `s.charAt(i)` is `[`, increment `i` to skip it, then make a recursive call to `decode()`. Append the returned string to `result` `count` times. Reset `count` to 0.
- If `s.charAt(i)` is a letter, append it to `result`.
- In all cases, increment `i`.
- When the loop terminates because `i` reaches the end of the string or a `]` is found, if it was a `]`, increment `i` to consume it.
- Return `result.toString()`.

## Iterative Approach with Two Stacks
This approach uses two stacks to iteratively decode the string, avoiding recursion. One stack stores the repetition counts (`countStack`), and the other stores the string being built before encountering a new nested scope (`stringStack`). This is generally the most robust and efficient method.
**Time:** O(M), where M is the length of the decoded output string. Each character is processed once, and string building operations are efficient with `StringBuilder`. The total work is proportional to the final string's length. · **Space:** O(M), where M is the length of the output string. The stacks can store intermediate strings and counts. The maximum total size of strings stored on the `stringStack` can be proportional to the final output string length M.
**Pros:** Efficient O(M) time complexity.; Avoids recursion, thus preventing potential stack overflow errors on extremely deep inputs.; Iterative solutions can have slightly better performance due to no function call overhead.
**Cons:** Requires managing two stacks, which might be slightly more complex to reason about than the recursive solution for some.
### Explanation
We iterate through the input string character by character. A `countStack` (of integers) and a `stringStack` (of `StringBuilder`s) are used. We also maintain `currentString` (`StringBuilder`) for the current level of decoding and `k` (integer) for the current repetition count. If the character is a digit, we update `k`. If the character is `[`, we push the current `k` onto `countStack` and the `currentString` onto `stringStack`. Then, we reset `k` and `currentString` to start a new scope. If the character is `]`, it signals the end of the current scope. We pop the state from the stacks and combine the strings. If the character is a letter, we simply append it to `currentString`. After iterating through the entire input string, `currentString` will hold the final decoded string.

```java
import java.util.Stack;

class Solution {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<StringBuilder> stringStack = new Stack<>();
        StringBuilder currentString = new StringBuilder();
        int k = 0;

        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                k = k * 10 + (ch - '0');
            } else if (ch == '[') {
                // Push the number k and the current string onto the stacks
                countStack.push(k);
                stringStack.push(currentString);
                // Reset for the new substring
                currentString = new StringBuilder();
                k = 0;
            } else if (ch == ']') {
                // Pop the state from the stacks
                StringBuilder decodedString = stringStack.pop();
                int repeatCount = countStack.pop();
                // Append the repeated current string to the decoded string
                for (int i = 0; i < repeatCount; i++) {
                    decodedString.append(currentString);
                }
                // This becomes the new current string
                currentString = decodedString;
            } else {
                currentString.append(ch);
            }
        }
        return currentString.toString();
    }
}
```
### Algorithm
- Initialize a `countStack` for integers and a `stringStack` for `StringBuilder`s.
- Initialize `currentString = new StringBuilder()` and `k = 0`.
- Iterate through each character `ch` of the input string `s`.
- If `ch` is a digit, update `k`: `k = k * 10 + (ch - '0')`.
- If `ch` is `[`, push `k` to `countStack`, push `currentString` to `stringStack`, and reset `k = 0` and `currentString = new StringBuilder()`.
- If `ch` is `]`, pop from `countStack` to get `repeatCount` and pop from `stringStack` to get `previousString`. Append `currentString` to `previousString` `repeatCount` times. Update `currentString` to be `previousString`.
- If `ch` is a letter, append it to `currentString`.
- After the loop, `currentString` holds the final result.

# Solutions
### Java

```java
class Solution {
public
  String decodeString(String s) {
    Deque<Integer> s1 = new ArrayDeque<>();
    Deque<String> s2 = new ArrayDeque<>();
    int num = 0;
    String res = "";
    for (char c : s.toCharArray()) {
      if ('0' <= c && c <= '9') {
        num = num * 10 + c - '0';
      } else if (c == '[') {
        s1.push(num);
        s2.push(res);
        num = 0;
        res = "";
      } else if (c == ']') {
        StringBuilder t = new StringBuilder();
        for (int i = 0, n = s1.pop(); i < n; ++i) {
          t.append(res);
        }
        res = s2.pop() + t.toString();
      } else {
        res += String.valueOf(c);
      }
    }
    return res;
  }
}

```

### Python

```python
class Solution:
    # initial, res being pushed is empty str '' num , res = 0 , '' elif c == ']' : res = str_stk . pop () + res * num_stk . pop () else : res += c return res
    def decodeString(self, s: str) -> str: num_stk, str_stk = [], [] num, res = 0, '' for c in s: if c . isdigit(): num = num * 10 + int(c) elif c == '[': num_stk . append(num) str_stk . append(res)

```