DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Decode String

mediumStack and queue

Problem statement

A string has been compressed with the rule k[text], which means "text repeated k times". k is a positive integer and can have more than one digit, and groups can be nested inside other groups. Letters outside any brackets are copied as they are.

Return the fully expanded string. You can assume the input is always well formed: brackets are balanced, every [ is directly preceded by its count, and digits only ever appear as counts.

Examples

Example 1

Input: s = "2[ab]c"

Output: "ababc"

Explanation: "ab" twice, then the plain "c".

Example 2

Input: s = "3[x2[y]]"

Output: "xyyxyyxyy"

Explanation: The inner group gives "yy", so each outer copy is "xyy", repeated three times.

Hints

Approach

One left-to-right pass with a stack.

  1. Keep current (the text of the group being built) and count (the number being read).
  2. Digit: count = count * 10 + digit, so 12[a] reads as twelve, not two.
  3. [: push (current, count) and reset both. The new group starts empty.
  4. ]: pop (before, k) and set current = before + current * k.
  5. Letter: append it to current.

At the end, current is the answer. Nested text gets copied once per level it is nested in, which is why the bound mentions the depth; for typical inputs this is close to linear in the output size.

ComplexityTime O(L * d), d = nesting depthSpace O(L)
Python
class Solution:
def decodeString(self, s: str) -> str:
stack = [] # (text built before this '[', repeat count for this group)
current = ""
count = 0
for ch in s:
if ch.isdigit():
count = count * 10 + int(ch) # counts can have several digits
elif ch == "[":
stack.append((current, count))
current, count = "", 0
elif ch == "]":
before, k = stack.pop()
current = before + current * k
else:
current += ch
return current

Follow-up questions

  • Reject malformed input such as 2[a or a] with a clear error instead of crashing.
  • The decoded string could be huge. How would you return only its length, or the character at position i, without building it?

Frequently asked questions

By the time you reach ], the digits are far behind you and other counts may have been read in between. Saving the count with the text you paused keeps each group's count paired with the right group.

Yes. A recursive function that reads until the matching ] and returns the expanded text is the same algorithm, with the call stack playing the role of the explicit stack. Very deep nesting can hit the recursion limit in Python.

It is a small parser with nesting, like expanding templated config, brace expansion in a shell (web-{01..03}), or nested placeholders in a deployment manifest. The stack of paused work is how those expanders handle nesting.