24. Decode String

You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:

A large messaging, content delivery, or configuration platform uses a compact encoding format to store repetitive text efficiently. This encoding reduces payload size for network transfer and storage, especially when a pattern repeats many times.

The encoding rule is:

• k[encoded_string] means the encoded_string is repeated exactly k times
• k is a positive integer
• Encoded strings can be nested

For example, "3[a2[c]]" expands to "accaccacc".

The encoded input is provided as a string s. Your job is to decode it into its fully expanded form.

This is a common practice coding problem for DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.

Your Task

Given an encoded string s, return its decoded string.

Rules:

• The input is always valid
• Digits represent repeat counts only when followed by [
• The decoded output does not contain digits, [ or ]

Input Format

• s: a string representing an encoded message

Output Format

• A string representing the fully decoded result

Examples

Constraints

• 1 <= s.length <= 30,000
• s consists of digits, English letters, and square brackets [ and ]
• 1 <= k <= 300
• The length of the decoded string will not exceed 200,000