Decode a recursively encoded string
Filed under Microsoft
Free read 2 of 3Brackets are well-formed. Digits indicate exact repeat counts for the enclosed substring.
The question
Given an encoded string where patterns like `k[encoded_string]` represent `encoded_string` repeated `k` times, return the fully decoded string. You may assume that the input string is always valid and digits represent repetition counts.
Constraints
- 1 <= s.length <= 300
- 1 <= k <= 300
- s consists of lowercase English letters, digits, and square brackets '[]'.
Examples
- Input
- s = "3[a2[c]]"
- Output
- "accaccacc"
- Why
- Inner bracket '2[c]' expands to 'cc'. '3[acc]' expands to 'accaccacc'.
- Input
- s = "2[abc]3[cd]ef"
- Output
- "abcabccdcdcdef"
- Why
- Decodes '2[abc]' to 'abcabc' and '3[cd]' to 'cdcdcd', appended with 'ef'.
Approach
Brackets are well-formed. Digits indicate exact repeat counts for the enclosed substring.
Use a stack to store previous string contexts and current repetition count k when encountering '['.
Build numbers on digits, push context on '[', pop and construct string on ']', and append chars otherwise.
Multi-digit k, empty brackets, and nested multi-level encoded blocks.
Solution
O(N) time, O(N) space
class Solution:
def decodeString(self, s: str) -> str:
stack = []
curr_str, curr_num = "", 0
for char in s:
if char.isdigit():
curr_num = curr_num * 10 + int(char)
elif char == '[':
stack.append((curr_str, curr_num))
curr_str, curr_num = "", 0
elif char == ']':
prev_str, num = stack.pop()
curr_str = prev_str + curr_str * num
else:
curr_str += char
return curr_str
Tips
- What they are testing: Assesses stack operations, string building, and nested recursive parsing logic.
- Common mistake: Failing to handle multi-digit numbers (e.g. '10[a]') or miscalculating stack pops for nested structures.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.