UnfolddArena

Decode String

Medium

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"

CompaniesMeta
JavaScript

Login to write code

Solve problems, verify your skills, and earn XP.