Decode String - Leetcode Solution

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; 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 won’t be input like 3a or 2[4].

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"

Example 4:

Input: s = "abc3[cd]xyz" Output: "abccdcdcdxyz"

Solution:

The given problem can be solved using a stack and a few pointers.

As the input string needs to be traversed character by character, we will use a pointer to keep track of the current position in the string.

Also, while parsing the string, we need to keep track of the count k of the current substring that needs to be repeated. We will use another pointer to keep track of k.

We will also use a stack to keep track of the previous substrings and their counts. Whenever we encounter an opening bracket, we will push the current count and substring to the stack and reset the count and substring to their initial state.

Whenever we encounter a closing bracket, we will pop the previous count and substring from the stack, repeat the current substring n times (where n is the count we just popped from the stack), and append it to the previous substring that we just popped from the stack.

We will continue this process until we reach the end of the input string.

Implementation:

Let's see how we can implement the solution in Python:

class Solution: def decodeString(self, s: str) -> str: stack = [] curr_str = "" curr_num = 0

    i = 0
    while i < len(s):
        if s[i].isdigit():
            curr_num = curr_num * 10 + int(s[i])
        elif s[i] == "[":
            stack.append((curr_num, curr_str))
            curr_num = 0
            curr_str = ""
        elif s[i] == "]":
            prev_num, prev_str = stack.pop()
            curr_str = prev_str + curr_str * prev_num
        else:
            curr_str += s[i]
        i += 1
        
    return curr_str

Time Complexity:

The time complexity of the above solution is O(n), where 'n' is the length of the input string.

Space Complexity:

The space complexity of the above solution is O(m), where 'm' is the maximum number of nested brackets in the input string. In the worst case, where all the characters in the input string are enclosed in brackets, the stack size can be equal to 'm'.

1