algoadvance

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. You may assume that the input string is always valid; no extra white spaces, square brackets are well-formed, etc.

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"

Clarifying Questions

1. Q: Are nested encodings possible?
   • A: Yes, nested encodings are possible as illustrated in the examples.
2. Q: Can we assume the input string is always correctly formatted?
   • A: Yes, you can assume the input string is always valid and well-formed.

Strategy

The problem contains nested structures and repeated patterns, which makes it apt for a stack based solution. Here is the strategy to decode the string:

1. Initialization:
   • Use a stack to keep track of characters and numbers.
   • Iterate through the input string, processing one character at a time.
2. Processing Characters:
   • If you encounter a digit, calculate the full digit (since it can be more than one character like 10).
   • If you encounter [, start a new segment.
   • If you encounter ], pop from stack until you get the matching [, decode the current segment, and repeat it according to the number on the top of the stack before the [.
3. Reconstructing String:
   • For characters and completed segments inside the stack, concatenate to form the final decoded string.

Code

def decodeString(s: str) -> str:
    stack = []
    current_num = 0
    current_string = ''
    
    for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)
        elif char == '[':
            # Push the current num and string to the stack
            stack.append(current_string)
            stack.append(current_num)
            # Reset current variables
            current_string = ''
            current_num = 0
        elif char == ']':
            # Pop the number first and then the string
            num = stack.pop()
            prev_string = stack.pop()
            # Build the new string
            current_string = prev_string + num * current_string
        else:
            current_string += char
            
    return current_string

Time Complexity

• Time Complexity: O(n), where n is the length of the input string. Each character in the string is processed once, and operations on the stack (push and pop) are O(1).
• Space Complexity: O(n), because in the worst case, the stack can store all characters of the string.

This solution efficiently handles the decoding of strings with nested and repeated encoded patterns using a stack-based approach.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?