Decompress encoded string with nested repeats

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.