Decode String

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

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.

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. When a ']' is encountered, the algorithm pops the last state, repeats the current substring accordingly, and appends it to the previous prefix. This approach cleanly handles arbitrary nesting and ensures linear time complexity.

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.

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