{x}
blog image

Decode String

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. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 105.

 

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

 

Constraints:

  • 1 <= s.length <= 30
  • s consists of lowercase English letters, digits, and square brackets '[]'.
  • s is guaranteed to be a valid input.
  • All the integers in s are in the range [1, 300].

Solution Explanation

This problem requires decoding a string encoded with the pattern k[encoded_string], where k is a positive integer and encoded_string is repeated k times. The solution uses a stack-based approach to handle nested encoded strings effectively.

Approach

The core idea is to use two stacks:

  1. s1 (Integer stack): Stores the repeat counts (k).
  2. s2 (String stack): Stores the decoded substrings.

The algorithm iterates through the input string s:

  • Digit: If a digit is encountered, it's appended to the current repeat count (num).
  • '[': When an opening bracket '[' is found:
    • The current repeat count (num) is pushed onto s1.
    • The current decoded string (res) is pushed onto s2.
    • The repeat count (num) and decoded string (res) are reset.
  • ']': When a closing bracket ']' is found:
    • The top repeat count (k) is popped from s1.
    • The top decoded substring (str) is popped from s2.
    • The current decoded string (res) is repeated k times and appended to str. This handles nested repetitions.
  • Character: If it's an alphabet character, it's appended to the current decoded string (res).

Time and Space Complexity Analysis

Time Complexity: O(N), where N is the length of the input string s. Each character is processed once. The string repetition operations inside the loop contribute linearly to the overall time complexity, although it can feel more expensive due to string concatenation.

Space Complexity: O(N) in the worst case. The maximum depth of the stacks can be proportional to the length of the string, particularly in cases of deeply nested brackets.

Code Implementation Details (Python3 example)

The Python3 code efficiently utilizes lists as stacks (s1, s2). The pop() and append() methods have O(1) complexity for lists. The string concatenation within the loop (res += c and res = s2.pop() + res * s1.pop()) can be optimized if extreme performance was absolutely crucial, but it does not significantly impact the overall complexity in this context given the problem constraints.

class Solution:
    def decodeString(self, s: str) -> str:
        s1, s2 = [], [] # Integer Stack, String Stack
        num, res = 0, '' # num: repeat count, res: decoded string
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == '[':
                s1.append(num)  # push repeat count
                s2.append(res) # push current decoded string
                num, res = 0, '' # reset
            elif c == ']':
                res = s2.pop() + res * s1.pop() # decode and append
            else:
                res += c # append character
        return res

The Java and TypeScript solutions follow similar logic, using Deque (Java) and an array (TypeScript) to implement the stacks. The core algorithm remains consistent across all languages.