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 Onsite rounds at Google.

What role is this question designed for?

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

Decompress encoded string with nested repeats

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given an encoded string, decompress it into its expanded form. Encoding rules: - Parentheses `(...)` denote a group. - A repetition count is written in braces `{n}` **immediately after** a closing parenthesis `)`. - The group `(...)` is repeated exactly `n` times. - Groups may be nested. - You may assume the input is valid: - Parentheses/braces are properly matched. - Every `{n}` appears right after a `)`. - No need to handle invalid edge cases. - `n` is an integer in the range **2 to 99**. Examples: 1) `"a(abc){3}" -> "aabcabcabc"` 2) `"a(b(c){2}){3}d" -> "abccbccbccd"` - `(c){2} -> "cc"` - `(b + "cc") -> "bcc"` - `(bcc){3} -> "bccbccbcc"` - add prefix/suffix: `"a" + "bccbccbcc" + "d"` Task: - Implement a function that takes the encoded string and returns the decompressed string. - State and justify the time and space complexity in terms of input length and output length.

Quick Answer: This question evaluates string parsing and manipulation skills, particularly handling nested repetition encodings and reasoning about output growth, and belongs to the Coding & Algorithms domain.

Given an encoded string `s`, return its decompressed form. Encoding rules: - Parentheses `(...)` denote a group. - A repetition count is written in braces `{n}` immediately after a closing parenthesis `)`. - The group `(...)` must be repeated exactly `n` times. - Groups may be nested. - Any character that is not part of the control syntax is copied as-is. - The input is guaranteed to be valid, so you do not need to handle malformed expressions. Examples: - `a(abc){3}` -> `aabcabcabc` - `a(b(c){2}){3}d` -> `abccbccbccd` Implement `solution(s)` to return the decompressed string.

Constraints

0 <= len(s) <= 100000
Each repetition count `n` is an integer from 2 to 99
Every `{n}` appears immediately after a `)`
Parentheses and braces are properly matched
The length of the decompressed output will not exceed 10^6 characters

Examples

Input: ("a(abc){3}",)

Expected Output: "aabcabcabc"

Explanation: The group `(abc)` expands to `abcabcabc`, and the leading `a` stays in front.

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

Expected Output: "abccbccbccd"

Explanation: `(c){2}` becomes `cc`, so `(bcc){3}` becomes `bccbccbcc`, then add the outer `a` and `d`.

Input: ("",)

Expected Output: ""

Explanation: An empty input decompresses to an empty string.

Input: ("plain",)

Expected Output: "plain"

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

Input: ("(ab){12}",)

Expected Output: "abababababababababababab"

Explanation: The group `ab` is repeated 12 times.

Input: ("(a){2}(b){3}",)

Expected Output: "aabbb"

Explanation: The first group becomes `aa`, and the second becomes `bbb`.

Hints

Use a stack to remember the already-built prefix whenever you enter a new parenthesized group.
When you reach `)`, parse the number inside the following braces, expand the current group, and append it back to the previous level.

Quick Overview

This question evaluates string parsing and manipulation skills, particularly handling nested repetition encodings and reasoning about output growth, and belongs to the Coding & Algorithms domain.