How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Instacart.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Instacart during technical interviews.

Decode an encoded string | Instacart Coding Question

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`.

Input: "2[ab3[c]]x"

Expected Output: "abcccabcccx"

Explanation: `3[c]` becomes `ccc`, so `ab3[c]` becomes `abccc`. Repeating twice gives `abcccabccc`, then append `x`.

Input: "abc"

Expected Output: "abc"

Explanation: There are no encoded patterns, so the string stays the same.

Input: "10[a]"

Expected Output: "aaaaaaaaaa"

Explanation: The substring `a` is repeated 10 times.

Input: ""

Expected Output: ""

Explanation: An empty input decodes to an empty string.

Hints

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.
Be careful with counts like `10[a]` or `23[bc]` — the number may have more than one digit.

Quick Overview

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