String Expansion
Filed under Amazon
Free read 3 of 3Confirm how nested structures behave and whether counts can be multiple digits (e.g., 12(a)).
The question
Given an encoded string containing letters and numbers in the format k(encoded_string) where the encoded string inside the brackets is repeated exactly k times, decode the string.
Constraints
- 1 <= s.length <= 30
- s consists of lowercase English letters, digits, and square brackets
- It is guaranteed that the input string is always valid
Examples
- Input
- s = "2(a3(bc))"
- Output
- "abcbcbcabcbcbc"
- Why
- The inner string "bc" is repeated 3 times to get "bcbcbc", prepended with 'a' to get "abcbcbc", and the entire result is repeated 2 times.
Approach
Confirm how nested structures behave and whether counts can be multiple digits (e.g., 12(a)).
Use regular expressions to repeatedly match and replace the innermost bracketed substring until no brackets remain, which is inefficient for deep nesting.
Use a stack to keep track of counts and previously built strings. When a closing bracket is encountered, pop the count and previous string to form the expanded segment.
Single character strings, strings without brackets, and deeply nested parentheses.
Tips
- What they are testing: Test nested brackets, multiple consecutive numbers, and strings with no brackets to verify the parser handles all layers correctly.
- Common mistake: Failing to handle multi-digit numbers properly by character-by-character parsing without accumulating digits.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.