Decode String

Decode String

What is this problem about?

The Decode String interview question asks you to expand a compressed string format. The encoding rule is k[encoded_string], which means the encoded_string inside the square brackets is being repeated exactly k times. k is guaranteed to be a positive integer. For example, 3[a]2[bc] should be decoded as aaabcbc. This Decode String coding problem involves handling nested structures, like 2[a3[b]].

Why is this asked in interviews?

This is an incredibly popular question at companies like Google, Bloomberg, and Adobe. it tests your proficiency with Stacks or Recursion. It evaluates how you handle nested logic and your ability to process tokens (numbers, brackets, and characters) in a single pass. It’s a mini-version of an expression parser or a compiler.

Algorithmic pattern used

This utilizes the Recursion, String, Stack interview pattern.

1. Iterative approach: Use two stacks—one for the repetition count (k) and one for the current string being built.
2. Token Processing:
   • If you see a digit, build the full number.
   • If you see [, push the current string and the number onto their respective stacks and reset the current string.
   • If you see a character, append it to the current string.
   • If you see ], pop the count and the previous string. Repeat the current string count times and prepend the previous string.

Example explanation

Input: 3[a2[c]]

1. Current: "", k=3. See [. Push "" and 3.
2. Current: "a", k=2. See [. Push "a" and 2.
3. Current: "c". See ]. Pop 2 and "a". Result: "a" + "c" * 2 = "acc".
4. Current: "acc". See ]. Pop 3 and "". Result: "" + "acc" * 3 = "accaccacc".

Common mistakes candidates make

• Multi-digit numbers: Only reading one character for k (e.g., failing on 10[a]).
• String Concatenation: Using repeated string addition in a loop, which can be very slow. Using a StringBuilder or list of strings is better.
• Nesting depth: Failing to correctly pop and merge strings when brackets are deeply nested.

Interview preparation tip

Practice both the stack-based and the recursive solutions. The recursive solution is often shorter and more elegant, while the stack-based one is sometimes easier to reason about for large inputs.