Question:

Implement a function decode_string(s: str) -> str that takes a string as input and decodes it based on the following rules:

• The input string will be encoded in the following format: [count1[string1]count2[string2]...]
• The count represents the number of times the corresponding string should be repeated.
• The decoded string should be the concatenation of the repeated strings.

Write the solution in Python.

Example:

assert decode_string("3[a]2[bc]") == "aaabcbc"
assert decode_string("2[abc]3[cd]ef") == "abcabccdcdcdef"
assert decode_string("2[a2[b]c]") == "abbcabbc"

Answer:

def decode_string(s: str) -> str:
    stack = []
    current_num = 0
    current_string = ''
    for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)  # Parsing multi-digit numbers
        elif char == '[':
            stack.append(current_string)
            stack.append(current_num)
            current_string = ''
            current_num = 0
        elif char == ']':
            num = stack.pop()
            prev_string = stack.pop()
            current_string = prev_string + num * current_string
        else:
            current_string += char
    return current_string

Explanation:

We will use a stack to decode the string. The stack will store the counts and previous strings encountered.

1. We initialize an empty stack, a variable current_num to keep track of the current count, and an empty string current_string to hold the current decoded substring.

2. We iterate over each character in the input string s.

3. If the current character is a digit, we convert it to an integer and add it to current_num after multiplying it by 10 (to handle multi-digit numbers).

4. If the current character is an opening square bracket [, it means we have encountered a new substring. We push the current count (current_num) and the previous substring (current_string) onto the stack, reset current_num to 0, and current_string to an empty string.

5. If the current character is a closing square bracket ], it means we have reached the end of a substring. We pop the previous string (prev_string) and count (num) from the stack, and update current_string to contain num copies of current_string concatenated with prev_string.

6. If the current character is neither a digit, nor an opening/closing square bracket, it means it is part of the substring. We append it to current_string.

7. Finally, after iterating through all characters in the input string, we return the final current_string, which contains the decoded string.