Quick Overview

Decode nested repetition syntax with saved prefix and count frames. Handle multi-digit counts, prove the stack invariant, and account honestly for expanded output and repeated string copying.

Decode Nested Repetition Strings with Stacks

Company: Compass

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Decode strings using the pattern k[encoded], where the bracketed content is repeated k times and may contain nested repetitions. Plain letters remain in order. ### Constraints and Clarifications The source identifies problem394. The [official Decode String reference](https://leetcode.com/problems/decode-string/description/) supplies this practice contract: valid syntax, lowercase letters, positive repeat counts from1 to300, encoded length1–30, and decoded length at most100000. Digits appear only in repeat counts, not as literal output characters. These are reference-context constraints, not additional recalled interview requirements. ### Example "2[a3[b]]c" decodes to "abbbabbbc". ### What a Strong Answer Covers Track multi-digit counts and nested contexts with stacks or equivalent frames. Explain what is saved at an opening bracket, what is restored at a closing bracket, and the cost of materializing expanded output. ### Follow-up Questions - Why does a single repeat counter fail for nested brackets? - How can repeated string concatenation affect complexity?

Overview: Decode nested repetition syntax with saved prefix and count frames. Handle multi-digit counts, prove the stack invariant, and account honestly for expanded output and repeated string copying.

Decode a valid string containing lowercase letters and repetitions of the form k[encoded], where the bracketed content is repeated k times. Repetitions may nest, and plain letters retain their order. Return the fully decoded string. For example, "2[a3[b]]c" becomes "abbbabbbc".

Constraints

  • Valid bracket syntax with lowercase literal letters.
  • Repeat counts are positive integers from 1 to 300; digits only occur in repeat counts.
  • Encoded length is 1 through 30, and decoded length is at most 100000.

Examples

Input: ('2[a3[b]]c',)

Expected Output: 'abbbabbbc'

Explanation: The inner three b characters are duplicated with each outer a.

Input: ('3[a]',)

Expected Output: 'aaa'

Explanation: One simple repetition.

Hints

  1. Save the current context when a new bracket opens.
  2. A count may contain more than one digit.

Loading coding console...

Show the approach

Approach

A stack stores the decoded prefix and repeat count at each opening bracket. The current segment is independent until its closing bracket, when it is repeated and appended to the saved prefix. Induction on bracket nesting shows that each completed segment equals its decoded source span. A separate count accumulator handles multi-digit counts. The output cap bounds materialization; repeated concatenation can copy intermediate strings.

Time complexity:
O(n * L) worst case for repeated string copying, where n is encoded length and L is decoded length
Space complexity:
O(L + n) for decoded segments and stack frames