Practice/Google/Leetcode 394. Decode String

Leetcode 394. Decode String

CodingMust

Problem

You are given an encoded string where certain substrings are marked for repetition using a special notation. The encoding format is k[substring], where k is a positive integer indicating how many times the substring should be repeated.

Your task is to decode and expand the entire string by processing all encoded patterns, including those that are nested within other patterns.

The encoded string follows these rules:

• Numbers indicate repetition counts and may be multi-digit (e.g., 10, 25)
• Square brackets [ and ] delimit the substring to be repeated
• Patterns can be nested arbitrarily deep
• Letters outside of brackets are taken literally
• The input string is always valid and well-formed

Return the fully decoded and expanded string.

Requirements

1. Process all repetition patterns in the string
2. Handle nested patterns correctly (innermost patterns should be expanded first)
3. Support multi-digit repetition counts
4. Preserve the order of characters in the final output
5. Handle literal characters that appear outside brackets

Constraints

• 1 ≤ s.length ≤ 30
• s consists of lowercase English letters, digits, and brackets [ ]
• s is guaranteed to be a valid encoding
• All integers in s are in the range [1, 300]
• The decoded string will not exceed 10^5 characters

Examples

Example 1:

Input: s = "3[a]2[bc]" Output: "aaabcbc" Explanation: "3[a]" expands to "aaa", and "2[bc]" expands to "bcbc". Concatenating gives "aaabcbc".

Example 2:

Input: s = "2[ab3[c]]" Output: "abcccabccc" Explanation: Start from innermost: "3[c]" becomes "ccc". Then "ab3[c]" becomes "abccc". Finally "2[abccc]" produces "abcccabccc".

Example 3:

Input: s = "x2[y]z" Output: "xyyyz" Explanation: The 'x' is literal, "2[y]" expands to "yy", and 'z' is literal.

Example 4:

Input: s = "10[a]" Output: "aaaaaaaaaa" Explanation: Multi-digit number 10 means repeat 'a' ten times.