Sign in to track progress, unlock prep layers, and browse your pipeline.Sign in
Decompress an encoded string
Problem Description
You are given an encoded string and must return its decoded (decompressed) form.
Encoding Rules
The encoding follows these rules:
- A positive integer
kfollowed by a bracketed substring[substring]indicates that thesubstringis repeatedktimes. - Encodings can be nested within other encodings.
Examples
- Input:
"3[a]2[bc]"Output:"aaabcbc" - Input:
"3[a2[c]]"Output:"accaccacc" - Input:
"2[abc]3[cd]ef"Output:"abcabccdcdcdef"
Assumptions
- The input string is always valid and well-formed according to the encoding rules.
- Digits within the string exclusively represent repeat counts (
k).
Deliverable
Return the fully decoded string.
AI interview prep
Core dilemma
Efficiently managing the state (current repeat count and string segment) across arbitrarily nested structures, while optimizing for potentially extremely large output string lengths and avoiding quadratic time complexity from naive string concatenations.
Mid-level signals3
Senior signals3
Red flags3
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Decompress an encoded string
Problem Description
You are given an encoded string and must return its decoded (decompressed) form.
Encoding Rules
The encoding follows these rules:
- A positive integer
kfollowed by a bracketed substring[substring]indicates that thesubstringis repeatedktimes. - Encodings can be nested within other encodings.
Examples
- Input:
"3[a]2[bc]"Output:"aaabcbc" - Input:
"3[a2[c]]"Output:"accaccacc" - Input:
"2[abc]3[cd]ef"Output:"abcabccdcdcdef"
Assumptions
- The input string is always valid and well-formed according to the encoding rules.
- Digits within the string exclusively represent repeat counts (
k).
Deliverable
Return the fully decoded string.