Katkat
Back

Expand Nested Repetition Expressions

WaymoSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to parse nested patterns and handle recursion or stack-based state management to expand strings defined by repetition rules.

Expand Nested Repetition Expressions

Given an encoded string, return its decoded version. The encoding rule is k[encoded_string], where the encoded_string inside the brackets is being repeated exactly k times. k is guaranteed to be a positive integer. You may assume that the input string is always valid.

Function Signature

def decode_string(s: str) -> str:
    pass

Constraints

  • 1 <= s.length <= 300
  • s consists of lowercase English letters, digits, and brackets [].
  • The nested depth is limited to 100.
  • The total length of the resulting string will not exceed 10^5 characters.

Examples

Example 1:

  • Input: s = "3[a]2[bc]"
  • Output: "aaabcbc"

Example 2:

  • Input: s = "3[a2[c]]"
  • Output: "accaccacc"

Example 3:

  • Input: s = "2[abc]3[cd]ef"
  • Output: "abcabccdcdcdef"

Edge Cases

  • Single digits vs multi-digit numbers (e.g., "12[a]").
  • No repetitions (e.g., "abc").
  • Deeply nested structures.

Hints

Hint 1

A stack can be used to keep track of the current repetition count and the string built so far before encountering a nested bracket.

Hint 2

Alternatively, you can use a recursive approach where you process the string index by index, incrementing the pointer as you descend into brackets.

Hint 3

When you encounter a number, parse the entire integer before proceeding; when you hit ']', return the accumulated string to the previous recursion level.

Follow-up questions

  • How would you modify your solution if the input format allowed nested expressions without numbers, such as 'a[b]c' representing 'abc'?
  • What is the time complexity of your solution in terms of the output string length?
  • How would you handle memory constraints if the expanded string is extremely large but follows a highly predictable pattern?