Decode String
Asked at TikTok
Problem
Decode String expands an encoded string where k[encoded] means the inside repeated k times, and encodings can be nested — "3[a2[c]]" becomes "accaccacc". It tests whether you can manage nested state cleanly with a stack (or recursion).
Asked At
| Company | Difficulty | |
|---|---|---|
| TikTok | Medium | View all TikTok questions → |
How to Think About It
Nesting means you cannot expand left to right in one flat pass — when you see ] you need to know which multiplier and which prefix it belongs to.
Key insight: use a stack of (prefix, multiplier) pairs. When you see [, push the string built so far and the number just read, then start a fresh current string. When you see ], pop and set current = prefix + current * multiplier.
Multipliers can have several digits ("12[a]"), so accumulate digits as num = num * 10 + digit and reset num after pushing.
Walkthrough for "3[a2[c]]": 3 -> num=3. [ push ("",3), cur="". a -> cur="a". 2 -> num=2. [ push ("a",2), cur="". c -> cur="c". ] pop ("a",2) -> cur="acc". ] pop ("",3) -> cur="accaccacc".
Letters outside any brackets are simply appended to the current string.
Optimal Approach
Step 1: stack = [], cur = "", num = 0.
Step 2: For each char ch:
If digit: num = num * 10 + int(ch).
If [: push (cur, num); reset cur = "", num = 0.
If ]: pop (prev, k); cur = prev + cur * k.
Otherwise (letter): cur += ch.
Step 3: Return cur.
Time: O(output length). Space: O(output length) including the stack.
What Trips People Up in Real Interviews
Assuming single-digit multipliers. "10[a]" must produce ten as — accumulate digits.
Forgetting to save the prefix before [. Without it, text before a nested block like the a in "2[a3[b]]" is lost.
Not resetting num after pushing it, so digits from the outer number leak into the inner one.
Using string concatenation in a tight loop in Java without a StringBuilder — it works but is slow for long outputs.
Solution Code
def decodeString(s):
stack = []
cur = ''
num = 0
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch)
elif ch == '[':
stack.append((cur, num))
cur, num = '', 0
elif ch == ']':
prev, k = stack.pop()
cur = prev + cur * k
else:
cur += ch
return curFrequently Asked Questions
What is the Decode String problem?
Decode String expands an encoded string where `k[encoded]` means the inside repeated `k` times, and encodings can be nested — `"3[a2[c]]"` becomes `"accaccacc"`. It tests whether you can manage nested state cleanly with a stack (or recursion).
How do you solve Decode String?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Decode String?
Decode String is asked at TikTok. It is a medium difficulty problem.
What are common mistakes on Decode String?
- Assuming single-digit multipliers. `"10[a]"` must produce ten `a`s — accumulate digits.
- Forgetting to save the prefix before `[`. Without it, text before a nested block like the `a` in `"2[a3[b]]"` is lost.
- Not resetting `num` after pushing it, so digits from the outer number leak into the inner one.
- Using string concatenation in a tight loop in Java without a `StringBuilder` — it works but is slow for long outputs.