#394

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Decode String

Decode a nested encoded string using stack-based state management, handling repeated patterns efficiently with recursion.

string stack recursion

Problem Statement

You are given an encoded string where repetitions are encoded as k[encoded_string], with k being a positive integer. Your task is to decode the string by expanding all repetitions and nested patterns according to the encoding rule.

The input string is guaranteed to be valid with properly matched brackets and contains only lowercase English letters, digits for repeat counts, and brackets. Return the fully decoded string after processing all nested and repeated segments correctly.

Examples

Example 1

Input: s = "3[a]2[bc]"

Output: "aaabcbc"

Example details omitted.

Example 2

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

Output: "accaccacc"

Example details omitted.

Example 3

Input: s = "2[abc]3[cd]ef"

Output: "abcabccdcdcdef"

Example details omitted.

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

Solution Approach

Iterative Stack-Based Solution

Use a stack to store previous strings and repeat counts. Traverse the string, pushing current partial strings and counts when encountering '['. Pop from the stack and expand the segment when ']' is found, concatenating with the previous string.

Recursive Depth-First Approach

Define a recursive helper that processes the string until a closing bracket. For digits, compute the repeat count, then recursively decode the substring inside brackets. Concatenate repeated decoded substrings with previous results.

Edge Case Handling

Ensure proper handling when multiple nested brackets occur, or when digits are more than one character. Validate that no stray digits or letters outside brackets are misinterpreted. Combine adjacent strings correctly after each recursive or stack expansion.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * maxK) where maxK is the maximum repeat count, as each character can be processed multiple times. Space complexity is O(n) for stack usage in the iterative solution or recursion call stack in the recursive solution.

What Interviewers Usually Probe

Expect the candidate to recognize nested repetition requires a stack or recursion.
Watch for mismanagement of multiple-digit repeat counts or nested brackets.
Look for concise handling of string concatenation to avoid repeated O(n^2) operations.

Common Pitfalls or Variants

Common pitfalls

Confusing digits inside the encoded string with repeat counts, leading to incorrect expansion.
Not correctly combining the previous string with repeated segments after popping from the stack.
Failing to handle multiple nested brackets or multi-digit repeat numbers properly.

Follow-up variants

Allowing digits in the encoded string itself, requiring different parsing logic.
Limiting the maximum depth of nested brackets to test iterative versus recursive solutions.
Encoding with different delimiters or adding optional separators inside repeats.

FAQ

What is the best approach to decode strings with nested k[encoded_string] patterns?

A stack-based iterative solution or recursive depth-first traversal ensures all nested patterns are expanded correctly.

How do I handle multi-digit repeat counts in Decode String?

Accumulate digits into a number before the '[' to capture full repeat counts before decoding the bracketed substring.

Can I solve Decode String without using a stack?

Yes, recursion can replace explicit stack management by leveraging the call stack to handle nested substrings.

What common mistakes occur with nested decoding?

Forgetting to concatenate repeated segments with previous strings or mishandling multiple nested brackets are frequent errors.

Why does Decode String require stack-based state management?

Because nested repetitions require tracking previous contexts and counts, and a stack efficiently preserves these states until each segment completes.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def decodeString(self, s: str) -> str:
        s1, s2 = [], []
        num, res = 0, ''
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == '[':
                s1.append(num)
                s2.append(res)
                num, res = 0, ''
            elif c == ']':
                res = s2.pop() + res * s1.pop()
            else:
                res += c
        return res

Continue Practicing

#224 basic calculator #736 parse lisp expression #770 basic calculator iv