Katkat
Back

Expand a Nested Repeat-Count Encoded String

AbridgeSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

From an Abridge online assessment: decode a string in which k[text] means the bracketed text repeated k times, with multi-digit counts, nested brackets and plain letters between encoded parts. It tests parsing nested structure correctly and building the expanded output efficiently.

You are given an encoded string s. The encoding rule is k[text]: the text inside the square brackets is repeated exactly k times, where k is a positive integer written in decimal. Encoded parts can be nested inside one another and can sit next to plain letters. Return the fully decoded string.

Function Signature

def decode(s: str) -> str:

Rules

  • s is always valid: brackets are balanced, every [ is immediately preceded by its repeat count, every repeat count is immediately followed by [, and no pair of brackets is empty.
  • Digits appear only as repeat counts, so the decoded string never contains digits.
  • A repeat count can have more than one digit (for example 12[a]) and has no leading zeros.
  • Letters outside every pair of brackets are copied to the output unchanged.

Constraints

  • 1 <= len(s) <= 30
  • s contains only lowercase English letters, digits, [ and ].
  • Every repeat count k satisfies 1 <= k <= 300.
  • The decoded string has length at most 100,000.

Examples

Example 1

Input: s = "2[x3[yz]]w"
Output: "xyzyzyzxyzyzyzw"

The inner part 3[yz] decodes to "yzyzyz", so x3[yz] is "xyzyzyz". That is repeated twice, and the trailing w is appended.

Example 2

Input: s = "z10[q]"
Output: "zqqqqqqqqqq"

The output is "z" followed by ten "q" characters; the repeat count has two digits.

Example 3

Input: s = "a2[b]c"
Output: "abbc"