How do you solve Decode String?

Iterate through the string character by character. Maintain a current prefix (as a list of characters) and a current number accumulator. When a digit is found, update the number. When '[' is found, push the current prefix and number onto the stack and reset them. When ']' is found, pop the previous prefix and repeat count, repeat the current prefix accordingly, and append it to the previous prefix. For letters, append them to the current prefix. Finally, join the current prefix into the decoded string. This stack-based approach runs in O(n + m) time, where m is the decoded output length.

Decode String

Q: What is the time complexity of Decode String?

O(n + m). Let n be the length of the input string and m be the length of the decoded output. The algorithm scans the input once (O(n)). Each closing bracket expansion must materialize decoded characters; across all expansions the total number of characters produced is m, so the total work for expansions is O(m). Therefore overall time is O(n + m).

Q: What pattern does Decode String use?

The Pattern: Stack (State Preservation for Nested Structures) The Heuristic: When decoding nested or hierarchical structures with matching delimiters, use a stack to save and restore context at each level, enabling clean, linear-time parsing of arbitrarily nested patterns.

Medium Stacks

Problem

Given an encoded string s, return its decoded string where the encoding rule is k[encoded_string], meaning the encoded_string inside the square brackets is repeated exactly k times. You may assume the input string is always valid and does not contain extra white spaces.

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

Example

Input: s = "3[a2[c]]"

Output: "accaccacc"

Example s = "3[a2[c]]" We scan left to right and maintain: - num: the repeat count we’re currently building (handles multi-digit like 12) - cur: the decoded text for the current bracket level, stored as a character list - stack: saved outer contexts as (prev_prefix_list, repeat_count) Start: num = 0, cur = [], stack = [] 1) Read "3" - This is a repeat count. - num = 3 2) Read "[" - We’re entering a bracketed block that will be repeated num times. - Save the current outer context, then start a fresh inner context: - stack.push(([], 3)) - Reset: cur = [], num = 0 3) Read "a" - Regular character, append to current level. - cur = ["a"] 4) Read "2" - Another repeat count for the next bracket. - num = 2 5) Read "[" - Enter a deeper nested block. Save what we have so far at this level. - stack.push((["a"], 2)) - Reset: cur = [], num = 0 6) Read "c" - Append letter. - cur = ["c"] 7) Read "]" (close inner block) - Pop the last saved context: prev = ["a"], k = 2 - Repeat the inner decoded chunk: ["c"] * 2 = ["c", "c"] - Stitch back into the previous prefix: ["a"] + ["c", "c"] = ["a", "c", "c"] - Now cur = ["a", "c", "c"] (we’re back inside the outer 3[...]) 8) Read "]" (close outer block) - Pop next context: prev = [], k = 3 - Repeat current chunk: ["a", "c", "c"] * 3 = ["a", "c", "c", "a", "c", "c", "a", "c", "c"] - Stitch back: [] + that = same list - Now cur = ["a", "c", "c", "a", "c", "c", "a", "c", "c"] End: - return ''.join(cur) -> "accaccacc"

Approach

Straightforward Solution

A naive approach might try to parse and decode the string recursively or with repeated string replacements, but this quickly becomes complex and inefficient, especially with nested patterns. Without a stack, managing nested contexts and repeat counts is error-prone.

Core Observation

The problem requires decoding nested repeated substrings, where each repeat count applies to the substring immediately following it inside brackets. The nested structure implies a last-in-first-out (LIFO) context management, naturally modeled by a stack.

Path to Optimal

Preview

Recognizing the nested, hierarchical structure of the encoding suggests using a stack to store the current prefix and repeat count before entering a new bracketed substring. Each time a '[' is encountered, the current state is pushed onto the stack, and a new context begins…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through the string character by character. Maintain a current prefix (as a list of characters) and a current number accumulator…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n + m)

Let n be the length of the input string and m be the length of the decoded output. The algorithm scans the input once (O(n)). Each closing bracket expansion must materialize decoded characters; across all expansions the total number of characters produced is m, so the total work for expansions is O(m). Therefore overall time is O(n + m).

Space

O(m + d)

Let m be the decoded output length and d be the maximum nesting depth. The output requires O(m) space. The stack stores up to d frames (previous prefix plus repeat count). Total space is O(m + d).

Pattern Spotlight

Stack (State Preservation for Nested Structures)

When decoding nested or hierarchical structures with matching delimiters, use a stack to save and restore context at each level, enabling clean, linear-time parsing of arbitrarily nested patterns.

Solution

Python

1class Solution:
  def decodeString(self, s: str) -> str:
      stack = []
      cur = []
      num = 0
6
      for c in s:
          if c.isdigit():
              num = num * 10 + int(c)
          elif c == '[':
              stack.append((cur, num))
              cur = []
              num = 0
          elif c == ']':
              prev, k = stack.pop()
              cur = prev + cur * k
          else:
              cur.append(c)
19
      return ''.join(cur)

Step-by-Step Solution

Initialize Stack and Current State Variables for Decoding

3stack = []
4cur = []
5num = 0

Objective

To set up the data structures and variables that track the decoding state as the string is processed.

Key Insight

The stack holds tuples of (previous_prefix, repeat_count) to preserve context when entering nested brackets. The current prefix is built as a list of characters for efficient concatenation, and the current number accumulates multi-digit repeat counts. This setup enables seamless transitions between nested levels.

Interview Quick-Check

Core Logic

Using a stack to store previous prefixes and repeat counts preserves the decoding context for nested brackets.

State & Boundaries

Initialize current prefix as a list and number as zero to handle incremental building and multi-digit numbers.

Common Pitfalls & Bugs

Failing to reset the current prefix and number after pushing onto the stack leads to incorrect concatenations.

Iterate Through Input String to Parse Digits, Brackets, and Characters

To process each character, updating the current number, pushing/popping stack states, and building the decoded string accordingly.

Return the Fully Decoded String by Joining Current Characters

To produce the final decoded string by concatenating all characters accumulated in the current prefix list.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 16 Critical

cur = prev + cur * k

Update the current prefix by concatenating the previous prefix with the current decoded substring repeated k times.

This concatenation embodies the core decoding logic, combining the repeated substring with the previously decoded prefix, enabling correct reconstruction of nested encoded patterns.

Line 9 Critical

num = num * 10 + int(c)

Update the current number by shifting previous digits and adding the new digit.

This line implements the critical logic for parsing multi-digit repeat counts, ensuring that numbers like '12' are correctly interpreted as twelve rather than separate digits.

Line 11 Critical

stack.append((cur, num))

Push the current prefix and number onto the stack to save context.

This push operation is the core mechanism that preserves the decoding context for nested brackets, allowing the algorithm to correctly resume previous states after decoding inner substrings.

Full line-by-line criticality + rationale for all 16 lines available on Pro.

Test Your Understanding

Why is a stack necessary to correctly decode nested encoded strings instead of using simple string concatenation or recursion without explicit state management?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Decode String from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Decode String drill

or drill a free problem

1	`class Solution:`
2	`def decodeString(self, s: str) -> str:`
3	`stack = []`
4	`cur = []`
5	`num = 0`
6
7	`for c in s:`
8	`if c.isdigit():`
9	`num = num * 10 + int(c)`
10	`elif c == '[':`
11	`stack.append((cur, num))`
12	`cur = []`
13	`num = 0`
14	`elif c == ']':`
15	`prev, k = stack.pop()`
16	`cur = prev + cur * k`
17	`else:`
18	`cur.append(c)`
19
20	`return ''.join(cur)`