Katkat
Back

Decompress encoded string with nested repeats

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to handle nested structures using recursion or a stack-based approach to expand string patterns based on repetition factors.

Decompress String

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.

Rules

  • You may assume the input string is always valid.
  • The number k may have multiple digits (e.g., 12[a] means a repeated 12 times).
  • The input can contain nested repetitions, such as 3[a2[c]] which becomes accaccacc.

Function Signature

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

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"

Constraints

  • 1 <= s.length <= 30
  • s consists of lowercase English letters, digits, and brackets [].
  • The total length of the decoded string will not exceed 10^5.

Edge Cases

  • No brackets (e.g., "abc" returns "abc").
  • Single digit vs multi-digit k.
  • Deeply nested structures.

Hints

Hint 1

Consider using a stack to keep track of the strings and repetition counts encountered so far.

Hint 2

When you encounter a closing bracket `]`, pop from the stack to find the most recent repetition count and the base string to multiply.

Hint 3

Alternatively, a recursive function can process the substring inside the brackets whenever a `[` is encountered.

Follow-up questions

  • What is the time complexity of your solution in terms of the length of the decoded output?
  • How would you modify your solution if the encoding format allowed for nested indices without brackets, like `3a2bc`?
  • How would you handle memory limits if the resulting decoded string is extremely large?