Katkat
Back

Implement Validation and String Compression

StripeSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to design a custom parser and recursive string processor that handles nested patterns while enforcing strict input validation.

Problem Statement

You are tasked with building a compression engine for a proprietary data format. The format consists of repeating patterns defined by the syntax k[string], where k is a positive integer and string is a sequence of characters or further nested k[string] patterns. The integer k represents the number of times the inner string should be repeated.

Your task is to implement a function decompress(s) that expands this string into its fully reconstructed form.

Constraints

  • s consists of digits, lowercase English letters, and square brackets [].
  • The input is guaranteed to be a validly formatted string.
  • The total number of nested levels is at most 10.
  • The final length of the decompressed string will not exceed 10^5 characters.

Examples

Example 1: Input: s = "3[a]2[bc]" Output: "aaabcbc" Explanation: The string "a" is repeated 3 times, followed by "bc" repeated 2 times.

Example 2: Input: s = "3[a2[c]]" Output: "accaccacc" Explanation: The inner "a2[c]" becomes "acc", then the entire group is repeated 3 times.

Function Signature

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

Hints

Hint 1

Consider using a stack to keep track of the current nesting level and the string prefixes being built.

Hint 2

When you encounter a closing bracket, pop the stack to find the corresponding multiplier and the string to be repeated.

Hint 3

Since the format is recursive, a depth-first search approach or maintaining a stack of (string_so_far, repeat_count) pairs is effective.

Follow-up questions

  • How would you modify your solution to handle cases where the input string might be malformed (e.g., missing brackets or invalid characters)?
  • What is the time and space complexity of your solution in terms of the length of the input string and the total number of characters in the output?
  • If the output size was expected to be significantly larger than memory (e.g., billions of characters), how would you design an iterator that produces the decompressed output lazily?