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

What role is this question designed for?

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

Expand Nested Repetition Expressions

Company: Waymo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a function that expands a valid encoded string containing nested parenthesized repetition expressions. Rules: - Ordinary characters are appended to the output as-is. - A group starts with `(` and ends with `)`. - Every closing parenthesis is immediately followed by a repetition count in the form `{k}`, where `k` is a positive integer. - The decoded contents of the group should be repeated exactly `k` times. - Groups may be nested. Examples: - Input: `"abs(cs){3}g"` - Output: `"abscscscsg"` - Input: `"a(b(c){2}){2}"` - Output: `"abccbcc"` Return the fully expanded string. You may solve this using either recursion or an explicit stack.

Quick Answer: This question evaluates understanding of string parsing and nested structure handling, including skills in recursion, stack-based parsing, tokenization, and managing repetition semantics.

Implement a function that expands a valid encoded string containing nested parenthesized repetition expressions. Rules: - Ordinary characters are appended to the output as-is. - A group starts with `(` and ends with `)`. - Every closing parenthesis is immediately followed by a repetition count in the form `{k}`, where `k` is a positive integer. - The decoded contents of the group should be repeated exactly `k` times. - Groups may be nested. Examples: - `"abs(cs){3}g"` expands to `"abscscscsg"` - `"a(b(c){2}){2}"` expands to `"abccbcc"` Return the fully expanded string. You may solve this using either recursion or an explicit stack.

Constraints

0 <= len(s) <= 10^5
The input string is always valid according to the given grammar
Each repetition count `k` is a positive integer
The total length of the expanded output will not exceed 10^6 characters

Examples

Input: "abs(cs){3}g"

Expected Output: "abscscscsg"

Explanation: The group `cs` is repeated 3 times, giving `abs` + `cscscs` + `g`.

Input: "a(b(c){2}){2}"

Expected Output: "abccbcc"

Explanation: Inner group `(c){2}` becomes `cc`, so outer group becomes `bcc`, repeated twice after the initial `a`.

Input: ""

Expected Output: ""

Explanation: An empty string expands to an empty string.

Input: "plain"

Expected Output: "plain"

Explanation: There are no repetition groups, so the string stays unchanged.

Input: "(ab){10}"

Expected Output: "abababababababababab"

Explanation: The group `ab` is repeated 10 times. This checks correct handling of multi-digit counts.

Input: "xy((zz){1}yw){3}q"

Expected Output: "xyzzywzzywzzywq"

Explanation: Inner `(zz){1}` becomes `zz`, so the outer group becomes `zzyw`, repeated 3 times, with `xy` before it and `q` after it.

Input: "(a(b){2}c){2}d"

Expected Output: "abbcabbcd"

Explanation: Inside the outer group, `(b){2}` becomes `bb`, so the group is `abbc`, repeated twice, then followed by `d`.

Hints

When you see `(`, solve the substring inside it first before applying the repetition count that follows `)`.
Track your current position in the string so nested groups can be parsed without rescanning characters.

Quick Overview

This question evaluates understanding of string parsing and nested structure handling, including skills in recursion, stack-based parsing, tokenization, and managing repetition semantics.