โ† Microsoft questions

Decode a recursively encoded string

Filed under Microsoft

Free read 2 of 3

Brackets 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

  1. Brackets are well-formed. Digits indicate exact repeat counts for the enclosed substring.

Solution

O(N) time, O(N) space

Python
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.