Skip to main content

394. Decode String

medium

Decode a string like '3[a2[c]]' into 'accaccacc'. The textbook two-stack problem for nested encodings — a frequent on-site warm-up before parser-heavy rounds.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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 10^5.

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

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two stacks: one for accumulated counts, one for accumulated strings.

Hint 2

On a digit: parse the full multi-digit number (it can be > 9).

Hint 3

On '[': push the count and the current built-string-so-far. Reset both for the new nesting level.

Hint 4

On ']': pop a count k and the previous string; result = previous + k * current. Set current to result.

Hint 5

On a letter: append it to the current build.

Solution approach

Reveal approach

Two stacks: a count-stack and a string-stack. Maintain a 'curStr' string and a 'curNum' integer as you scan. For each char c: if c is a digit, curNum = curNum * 10 + int(c) (handles multi-digit). If c == '[', push curNum and curStr, then reset both. If c == ']', pop k from count-stack and prevStr from string-stack; set curStr = prevStr + k * curStr. Otherwise (letter), curStr += c. Return curStr after the scan. O(n * m) time where m is the output length / n. Single-pass recursive-descent works too, but the two-stack iterative version is the cleanest to whiteboard.

Complexity

Time
O(N) where N is the output length
Space
O(N)

Related patterns

  • stack
  • string
  • recursion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Bloomberg
  • Google
  • Meta

Practice these live with InterviewChamp.AI

Drill Decode String and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →