Solution: Decode String

Statement

Given an encoded string, return its decoded version. The encoding rule follows the pattern: $k[encoded~string]$, where the $encoded~string$ is repeated exactly $k$ times.

Note: The $k$ is guaranteed to be a positive integer.

Assume that the input string is always valid, meaning there are no extra spaces, and the square brackets are properly balanced and well-formed. Additionally, assume that the original data contains no digits and that digits are only used for repeating the string.

For example, the input will not contain patterns like $3a$ or $2[4]$, whereas a valid pattern is $2[aj]3[bax]$.

Constraints:

• $1 \leq$ s.length $\leq 30$

• $1 \leq$ $k$ $\leq 100$

• s consists of lowercase English letters, digits, and square brackets.

Solution

The essence of this approach lies in recognizing that the problem is naturally suited for a stack-based solution. When decoding a string, we need to handle nested and sequential patterns, and a stack allows us to manage these layers effectively. By pushing and popping elements on the stack as we encounter brackets, we can keep track of the substrings and their repeat counts. This method ensures we decode the string from the innermost nested structure outward, maintaining the correct order and repetition. To achieve this, we process each character in the string in the following way:

• Digits: Represent how many times a substring is repeated.

• Open bracket ([): Marks the start of a new substring and saves the current state by pushing the current substring and repeat count onto stacks and then resetting them for a new segment.

• Close bracket (]): Ends the current substring, repeats it as specified, and appends it to the previous substring.

• Letters: Build the current substring being processed.

This solution handles nested and consecutive encoding strings by utilizing the stack to track previously processed substrings and their associated repeat counts. The final decoded string is constructed by combining all parts accumulated in the stacks.

Here’s the step-by-step implementation of the solution:

• Initialize two empty stacks: count_stack for storing repeat counts and string_stack for storing intermediate strings.

• Initialize current as an empty string. This will hold the currently decoded string segment.

• Initialize k as 0: This will store multi-digit numbers representing repeat counts.

• Iterate through each character char in the input string s:

  • If char is a digit:

    • Update k to accumulate the digit into a multi-digit number by performing k = 10 * k + int(char).

  • If char is a '[':

    • Push k onto count_stack to save the current repeat count.

    • Push current onto string_stack to save the current string segment.

    • Reset k to $0$ for the next repeat count.

    • Reset current to an empty string to start decoding the new segment.

  • If char is a’]’:

    • Pop the last string segment from string_stack and store it in decoded_string.

    • Pop the last repeat count from count_stack and store it in num.

    • Update current by appending current * num to decoded_string, repeating the decoded segment, and combining it with the previous string.

  • If char is a regular character:

    • Append char to current, adding it to the currently decoded string segment.

• After processing all characters, current will contain the fully decoded string.

Let’s look at the following illustration to get a better understanding of the solution: