Decode String | Leetcode 394

Welcome to our deep dive on Decode String (Leetcode 394). This fundamentally challenges your ability to parse nested bracket structures, making it the perfect problem for a Stack.

Problem Statement

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc.

Example 1: s = "3[a]2[bc]" => Output: "aaabcbc"

Example 2: s = "3[a2[c]]" => Output: "accaccacc"

Approach: The Two-Stack Solution O(N)

Whenever you see nested boundaries like [ ] that need to be evaluated from the inside out, a Stack (or recursion, which uses the call stack) is the ideal tool. Because a string can contain both numbers (k) and letters, it's often cleanest to use two arrays/stacks: one for the multipliers, and one for the active string building.

1. Maintain an active curr_str and an active curr_num.
2. Iterate character by character:
   • If it's a digit: Add it to curr_num. Since numbers can be multiple digits (like 120[a]), multiply curr_num * 10 before adding the new digit.
   • If it's a letter: Append it to curr_str.
   • If it's an open bracket [: We are diving into a nested level! We must push our existing curr_str and existing curr_num onto their respective stacks to save them for later. Then, reset curr_str to "" and curr_num to 0 to start building the inside of the bracket.
   • If it's a closing bracket ]: We have finished building the inside level string! Pop the multiplier k from the number stack. Multiply curr_str by k. Then, pop the previous string from the string stack, and append our newly multiplied string to it. This combined result becomes the new curr_str!

class Solution:
    def decodeString(self, s: str) -> str:
        num_stack = []
        str_stack = []
        curr_str = ""
        curr_num = 0
        
        for char in s:
            if char.isdigit():
                curr_num = curr_num * 10 + int(char)
            elif char.isalpha():
                curr_str += char
            elif char == '[':
                # Save the current state and reset
                num_stack.append(curr_num)
                str_stack.append(curr_str)
                curr_num = 0
                curr_str = ""
            elif char == ']':
                # Decode the innermost string
                multiplier = num_stack.pop()
                prev_str = str_stack.pop()
                
                # Append the multiplied string to the previous string
                curr_str = prev_str + (curr_str * multiplier)
                
        return curr_str

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (394)