Katkat
Back

Decode an encoded string

InstacartSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates string parsing and manipulation skills, particularly handling nested repetition encodings and managing state when expanding bracketed substrings.

Implement a decoder for an encoded string where repetition is expressed with a number followed by a bracketed substring.

Rules:

  • A pattern k[substring] means substring repeated k times.
  • Patterns can be nested.
  • Characters outside brackets are literal.
  • k is a positive integer.

Examples:

  • Input: "3[a]2[bc]" → Output: "aaabcbc"
  • Input: "3[a2[c]]" → Output: "accaccacc"
  • Input: "2[ab3[c]]x" → Output: "abcccabcccx"

Return the decoded string.