Decode String

Difficulty: Medium Source: NeetCode

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 all the digits are only for those repeat numbers, k.

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 '[]'.

It is guaranteed that s is valid (parentheses are properly closed, k > 0).

There are no extra white spaces.

Prerequisites

Before attempting this problem, you should be comfortable with:

Stack — Used to save the “context” (current string and repeat count) when entering a nested bracket group.
String building — Understanding how to accumulate characters and expand repeated substrings.

The tricky part is nesting — 3[a2[c]] means you need to decode the inner 2[c] first before repeating the outer. A stack naturally handles nesting: when you see [, save your current state (the string built so far and the repeat count) on the stack and start fresh. When you see ], pop the saved state, expand the current string by the saved count, and append it to what you had before.

Algorithm

Initialize current_str = "", current_num = 0, and an empty stack.
For each character c:
- If c is a digit: current_num = current_num * 10 + int(c) (handles multi-digit numbers).
- If c == '[': push (current_str, current_num) onto the stack, reset both to "" and 0.
- If c == ']': pop (prev_str, num), set current_str = prev_str + num * current_str.
- Otherwise (a letter): append c to current_str.
Return current_str.

Solution

def decodeString(s):
    stack = []         # stores (string_so_far, repeat_count) tuples
    current_str = ""
    current_num = 0

    for c in s:
        if c.isdigit():
            # Build up the number (could be multi-digit like "12[...]")
            current_num = current_num * 10 + int(c)
        elif c == "[":
            # Save current context and start a new group
            stack.append((current_str, current_num))
            current_str = ""
            current_num = 0
        elif c == "]":
            # Expand: pop context, repeat current string, attach to previous
            prev_str, num = stack.pop()
            current_str = prev_str + num * current_str
        else:
            # Regular letter
            current_str += c

    return current_str


# Test cases
print(decodeString("3[a]2[bc]"))       # Expected: "aaabcbc"
print(decodeString("3[a2[c]]"))        # Expected: "accaccacc"
print(decodeString("2[abc]3[cd]ef"))   # Expected: "abcabccdcdcdef"
print(decodeString("abc"))             # Expected: "abc"     (no encoding)
print(decodeString("10[a]"))           # Expected: "aaaaaaaaaa"  (multi-digit k)
print(decodeString("2[3[a]b]"))        # Expected: "aaabaaab"    (nested)

Complexity

Time: O(n * k) where n is the length of the output — each character in the final decoded string is written at most once per nesting level, but the repeated string construction can make it proportional to the output size.
Space: O(n) — the stack depth is bounded by the nesting depth, and current_str can grow to the full output size.

Common Pitfalls

Forgetting multi-digit numbers. A number like 12 appears as two separate digit characters. Build it up with current_num = current_num * 10 + int(c) rather than overwriting.

Resetting state on [ but forgetting to reset current_num too. After pushing onto the stack, both current_str and current_num need to be reset to empty string and zero for the new group.

Using str * 0 accidentally. The problem guarantees k >= 1, but if current_num were somehow 0 (e.g., you forgot to parse a digit), the inner string would be silently dropped. Make sure every [ is preceded by a valid digit sequence.

Note Book