Quick Overview

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

Decode an encoded string

Company: Instacart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

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

Given a valid encoded string `s`, return its decoded form. Encoding follows this rule: `k[substring]` means the `substring` inside the brackets is repeated exactly `k` times, where `k` is a positive integer. Additional rules: - Patterns may be nested. - Characters outside brackets are treated as literal characters. - The input string is guaranteed to be valid. Examples: - `"3[a]2[bc]"` becomes `"aaabcbc"` - `"3[a2[c]]"` becomes `"accaccacc"` - `"2[ab3[c]]x"` becomes `"abcccabcccx"`

Constraints

  • `0 <= len(s) <= 10^5`
  • `s` contains only letters, digits, `[` and `]`
  • Every bracketed pattern is valid and every repeat count is a positive integer
  • The length of the decoded string will not exceed `10^6`

Examples

Input: "3[a]2[bc]"

Expected Output: "aaabcbc"

Explanation: `3[a]` becomes `aaa` and `2[bc]` becomes `bcbc`, so the final result is `aaabcbc`.

Input: "3[a2[c]]"

Expected Output: "accaccacc"

Explanation: Inside the outer pattern, `a2[c]` becomes `acc`. Repeating that 3 times gives `accaccacc`.

Hints

  1. Use a stack to remember the string built so far and the repeat count when you encounter `[`. When you see `]`, you can expand the current segment.
  2. Be careful with counts like `10[a]` or `23[bc]` — the number may have more than one digit.

Loading coding console...