Decode String

Problem Statement

Given a string

s

containing only lowercase English letters and digits, and a string

s

encoded in a specific way, decode the string back into its original form.

The original string may have been encoded by using numbers and letters to represent repetitions of strings. Specifically, every substring that can be expressed as a repeat of a string will be expressed as a

num

followed by a

letter

, where

num

is the number of repetitions and

letter

is the string being repeated.

s = encoded_string, encoded_string = s[0]
if(i==0)
s = num + letter
else
s = s[0...num].repeat(num) + letter 

Rules and Constraints

The input
s
will contain only lowercase English letters (
a-z
) and digits (
0-9
).
Numbers will not have leading zeros (i.e.,
00
is not a valid number in
s
).
No invalid operations like divide by zero or taking the root of a negative number will occur.
The output should be the decoded string.

Time Complexity

O(n), where n is the length of
s
, to traverse through the string once.

Space Complexity

O(n), additional space to store the intermediate decoded string.

Note that these complexities assume the use of a stack to store the intermediate decoded strings.

Example

Input: {"s":"3[a2[c]]"} Output: "accaccacc"