Decode String - Python Solution

1. Introduction

The "Decode String" problem is a fascinating string manipulation challenge, which involves decoding a string following a specific encoding rule. The rule is based on repeating a certain part of the string a given number of times. This problem tests the ability to use stacks and understand string processing in depth.

Problem

Given an encoded string, the task is to return its decoded string. The encoding rule is k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. k is always a positive integer. The input string is always valid, with no extra white spaces, well-formed brackets, and digits only for repeat numbers.

2. Solution Steps

1. Initialize a stack to keep track of the characters and repeat counts.

2. Iterate through each character of the string.

3. When a digit is encountered, calculate the repeat count.

4. When an opening bracket '[' is encountered, push the current repeat count and the result formed so far onto the stack, then reset them.

5. When a closing bracket ']' is encountered, pop the top element from the stack to get the string and repeat count before the opening bracket and append the repeated string to the result.

6. Continue processing until the end of the string.

7. Return the decoded string.

3. Code Program

def decodeString(s):
    stack = []
    current_string = ''
    current_num = 0

    for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)
        elif char == '[':
            stack.append((current_string, current_num))
            current_string, current_num = '', 0
        elif char == ']':
            prev_string, num = stack.pop()
            current_string = prev_string + num * current_string
        else:
            current_string += char

    return current_string

# Example Usage
print(decodeString("3[a2[c]]"))   # Output: "accaccacc"
print(decodeString("2[abc]3[cd]ef")) # Output: "abcabccdcdcdef"

Output:

"accaccacc"
"abcabccdcdcdef"

Explanation:

1. Stack Usage: A stack is used to track previous states before each '['.

2. Digit Processing: Consecutive digits are processed to form the repeat count.

3. Opening Bracket: Upon encountering '[', current state is pushed onto the stack.

4. Closing Bracket: When ']' is encountered, the string inside the brackets is repeated and appended.

5. Efficient Solution: The algorithm efficiently processes the string in O(n) time complexity.

6. String Building: Characters are appended to form the current string being processed.

7. Final Decoded String: The complete decoded string is returned at the end.