Decode String
Unpack a compressed text banner. A banner is stored as plain letters mixed with groups written count[chunk]: the chunk inside the brackets is printed count times in a row. A chunk can hold letters and more groups, and a count can have several digits, like 12[ab]. Letters outside any group are printed once, in place. Return the fully unpacked banner. Limits: 1 to 1,000,000 characters in s, made of letters (a-z, A-Z), counts of 1 or more, and balanced brackets with something inside each pair. The unpacked banner has at most 1,000,000 characters, and groups nest at most 200 deep. Rebuilding the whole string after every group is far too slow at that size. Think about: what do you need to remember when you step inside a bracket? And joining two strings copies both, so how often is each letter copied? Example: "2[ab3[x]]y" => "abxxxabxxxy" (3[x] is xxx, the chunk becomes abxxx, it runs twice, then y) "10[q]" => "qqqqqqqqqq" (a count can have more than one digit) "k2[o]p" => "koop" (letters outside a group stay where they are)
You're unpacking a compressed message where a number in front of a bracket means repeat what's inside that many times, and groups can sit inside other groups. Interviewers love it because the nesting begs for a stack, and the real test is staying calm when a count has several digits or letters trail a closing bracket. The classic trap is rebuilding the whole string after every group, which crawls on long input. Expect up to 1,000,000 characters in and up to 1,000,000 out.
Examples
You write
decode_string(s: str)
Example 1
- Input
- s = "2[ab3[x]]y"
- returns
- "abxxxabxxxy"
Example 2
- Input
- s = "10[q]"
- returns
- "qqqqqqqqqq"
Save this for your laptop
The editor and Run need a bigger screen. The link opens Decode String ready to code. It is free, and the editor needs no account.
The pattern behind it
Stack
I reach for it when
- Things must close in the reverse order they opened.
- You need the nearest earlier or later item that is bigger or smaller.
Say this before you type. Say what each item on the stack is waiting for, and what lets you pop it.
All 16 Stack problemsStrings
I reach for it when
- The input is text and the answer is a count, a substring or a new string.
- You need to compare, reverse or rebuild characters.
Say this before you type. Say which array pattern the string is hiding before you touch a character.
All 49 Strings problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.