Decode String

▶

Steps

setup

Initialize variables

Initialize empty count_stack and string_stack, set current_string to empty list, and k (repeat count) to 0.

💡 Starting with empty stacks and variables prepares to process the input string character by character.

Line:

count_stack = []
string_stack = []
current_string = []
k = 0

💡 The algorithm uses separate stacks to track counts and partial strings, and a variable k to build multi-digit counts.

traverse

Read digit '3', build repeat count

Read character '3', which is a digit, so update k = 0 * 10 + 3 = 3.

💡 Digits can be multiple characters, so k accumulates the full repeat count before '['.

Line:

if char.isdigit():
    k = k * 10 + int(char)

💡 The algorithm correctly handles multi-digit repeat counts by accumulating digits into k.

push

Encounter '[', push count and current string

On '[', push current k=3 onto count_stack and current_string=[] onto string_stack, then reset current_string and k.

💡 Pushing saves the current context before decoding the substring inside brackets.

Line:

elif char == '[':
    count_stack.append(k)
    string_stack.append(current_string)
    current_string = []
    k = 0

💡 Stacks store the context so nested substrings can be decoded independently.

fill_cells

Append character 'a' to current string

Read character 'a', which is a letter, so append it to current_string.

💡 Letters build the substring that will be repeated later.

Line:

else:
    current_string.append(char)

💡 The current_string accumulates characters inside the current bracket level.

pop

Encounter ']', pop and repeat substring

On ']', pop last string (empty list) and count (3), then update current_string = prev_string + current_string * count = [] + ['a']*3 = ['a','a','a'].

💡 Popping applies the repeat count to the substring just built inside brackets.

Line:

elif char == ']':
    prev_string = string_stack.pop()
    count = count_stack.pop()
    current_string = prev_string + current_string * count

💡 This step decodes one bracketed substring fully and merges it with previous context.

traverse

Read digit '2', build repeat count

Read character '2', a digit, so update k = 0 * 10 + 2 = 2.

💡 Start building the next repeat count for the following bracketed substring.

Line:

if char.isdigit():
    k = k * 10 + int(char)

💡 The algorithm resets k after each bracketed substring to handle multiple repeats.

push

Encounter '[', push count and current string

On '[', push current k=2 onto count_stack and current_string=['a','a','a'] onto string_stack, then reset current_string and k.

💡 Save current decoded string and repeat count before decoding next substring.

Line:

elif char == '[':
    count_stack.append(k)
    string_stack.append(current_string)
    current_string = []
    k = 0

💡 Stacks keep track of nested decoding contexts.

fill_cells

Append character 'b' to current string

Read character 'b', append it to current_string.

💡 Building substring inside the second bracket.

Line:

else:
    current_string.append(char)

💡 Characters accumulate in current_string until ']' is encountered.

fill_cells

Append character 'c' to current string

Read character 'c', append it to current_string.

💡 Continue building substring inside brackets.

Line:

else:
    current_string.append(char)

💡 The substring inside brackets is 'bc'.

pop

Encounter ']', pop and repeat substring

On ']', pop last string ['a','a','a'] and count 2, then current_string = prev_string + current_string * count = ['a','a','a'] + ['b','c']*2 = ['a','a','a','b','c','b','c'].

💡 Repeat the substring inside brackets and merge with previous decoded string.

Line:

elif char == ']':
    prev_string = string_stack.pop()
    count = count_stack.pop()
    current_string = prev_string + current_string * count

💡 This completes decoding of the entire input string.

reconstruct

End of input, return decoded string

All characters processed, join current_string list into final string 'aaabcbc' and return.

💡 Joining the list of characters produces the final decoded output.

Line:

return ''.join(current_string)

💡 The algorithm successfully decoded the input using stacks and string building.

def decodeString(s: str) -> str:
    count_stack = []  # STEP 1
    string_stack = []  # STEP 1
    current_string = []  # STEP 1
    k = 0  # STEP 1
    for char in s:
        if char.isdigit():  # STEP 2,6
            k = k * 10 + int(char)  # STEP 2,6
        elif char == '[':  # STEP 3,7
            count_stack.append(k)  # STEP 3,7
            string_stack.append(current_string)  # STEP 3,7
            current_string = []  # STEP 3,7
            k = 0  # STEP 3,7
        elif char == ']':  # STEP 5,10
            prev_string = string_stack.pop()  # STEP 5,10
            count = count_stack.pop()  # STEP 5,10
            current_string = prev_string + current_string * count  # STEP 5,10
        else:  # STEP 4,8,9
            current_string.append(char)  # STEP 4,8,9
    return ''.join(current_string)  # STEP 11

📊

Decode String - Watch the Algorithm Execute, Step by Step

Watching this step-by-step reveals how the stacks coordinate to handle nested and repeated substrings, which is hard to grasp from code alone.

no_opElement[0]: 3

Stack (top→bottom)

empty

no_opElement[1]: [

Stack (top→bottom)

empty

pushElement[2]: a

Stack (top→bottom)

{"count_stack":[3],"string_stack":[[]]}

↑ pushed: 3

no_opElement[3]: a

Stack (top→bottom)

{"count_stack":[3],"string_stack":[[]]}

popElement[4]: 2

Stack (top→bottom)

empty

↓ popped: [3, ]

Contributes: "aaa"

no_opElement[5]: [

Stack (top→bottom)

empty

Contributes: "aaa"

pushElement[6]: b

Stack (top→bottom)

{"count_stack":[2],"string_stack":[["a","a","a"]]}

↑ pushed: 2

Contributes: "aaa"

no_opElement[7]: b

Stack (top→bottom)

{"count_stack":[2],"string_stack":[["a","a","a"]]}

Contributes: "aaa"

no_opElement[8]: c

Stack (top→bottom)

{"count_stack":[2],"string_stack":[["a","a","a"]]}

Contributes: "aaa"

pop

Stack (top→bottom)

empty

↓ popped: [2, a,a,a]

Contributes: "aaabcbc"

no_op

Stack (top→bottom)

empty

Contributes: "aaabcbc"

Key Takeaways

✓ Stacks separate repeat counts and partial strings, enabling nested decoding.

This separation is subtle in code but clear when watching push/pop operations.

✓ The algorithm accumulates digits into k to handle multi-digit repeat counts correctly.

Seeing k build up step-by-step clarifies how counts like '12' are parsed.

✓ Popping stacks on ']' applies the repeat count and merges substrings, completing nested decoding.

Watching the pop and string multiplication reveals how nested repeats are resolved.

Practice

1. You are given a numeric string num and an integer k. The task is to remove exactly k digits from num to produce the smallest possible number. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Greedy algorithm using a monotonic increasing stack to remove digits that are greater than the next digit

B. Dynamic Programming that tries all subsequences of length n-k and picks the smallest lexicographically

C. Simple greedy approach removing the largest digits from left to right without considering order

D. Brute force generating all combinations of digits to remove and selecting the minimal result

Solution

1. Step 1: Understand the problem constraints

   The problem requires removing digits to minimize the resulting number, which suggests a greedy approach that considers digit order.

2. Step 2: Identify the optimal approach

   Using a monotonic increasing stack allows removing digits that are larger than the next digit, ensuring the smallest possible number in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is known optimal for this problem [OK]

Hint: Monotonic stack greedily removes bigger digits before smaller ones [OK]

Common Mistakes:

• Assuming simple greedy removing largest digits left to right is optimal
• Thinking DP is needed for minimal number subsequence

2. Given the following Python code for checking valid parentheses, what is the return value when the input string is "([)]"?

def isValid(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:
            return False
    return not stack

easy

A. False

B. True

C. Raises an exception

D. Depends on input length

Solution

1. Step 1: Trace input "([)]" through the code

   Push '(' then push '['. Next char is ')', expected to match '[' but pairs[')'] = '(', top of stack is '[' -> mismatch -> return False immediately.

2. Step 2: Confirm final output

   Function returns False as soon as mismatch is detected.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mismatch detected at third character -> returns False [OK]

Hint: Mismatch causes immediate False return [OK]

Common Mistakes:

• Assuming order doesn't matter and returning True incorrectly

3. What is the time complexity of the optimal maximalRectangle solution that uses row-wise histogram transformation and largestRectangleArea with a monotonic stack for a matrix of size rows x cols?

medium

A. O(rows^2 * cols^2)

B. O(rows * cols^2)

C. O(rows^2 * cols)

D. O(rows * cols)

Solution

1. Step 1: Analyze outer loop over rows and inner loop over columns

   For each row, heights array is updated in O(cols) time.

2. Step 2: Analyze largestRectangleArea call per row

   largestRectangleArea uses a monotonic stack with O(cols) amortized time per call.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Each row processed in O(cols), total O(rows * cols) [OK]

Hint: Each row processed once, stack operations amortize to O(cols) [OK]

Common Mistakes:

• Confusing nested loops leading to O(rows * cols^2)
• Assuming stack operations are O(cols^2)
• Forgetting amortized analysis

4. What is the time complexity of the optimized stack-based approach for validating parentheses in a string of length n, and why might some candidates mistakenly think it is higher?

medium

A. O(n^2) because each character might be compared multiple times during matching

B. O(n) because each character is processed once with constant-time stack operations

C. O(n log n) due to sorting or ordering operations on the stack

D. O(n) for time but O(n^2) for space due to stack growth in worst case

Solution

1. Step 1: Identify complexity of outer loop

   The algorithm iterates over each character exactly once, so the loop is O(n).

2. Step 2: Check stack operations

   Stack push/pop are O(1) operations, so total time remains O(n). No nested loops or repeated scanning.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with constant-time stack ops -> O(n) time [OK]

Hint: Each character processed once with O(1) stack ops [OK]

Common Mistakes:

• Confusing with brute force O(n^2) approach

5. Suppose the problem is modified so that the input string may contain wildcard characters '*' that can represent either an opening bracket, a closing bracket, or an empty string. Which of the following approaches correctly adapts the stack-based solution to handle this variant efficiently?

hard

A. Use a brute force approach to try all replacements of '*' and check validity

B. Replace all '*' with empty strings and run the original stack-based validation

C. Use two stacks to track possible opening and closing brackets positions and validate ranges

D. Ignore '*' characters and validate only the remaining brackets with the original stack approach

Solution

1. Step 1: Understand wildcard impact

   Wildcards can represent multiple bracket types or empty, so a single stack is insufficient to track all possibilities.

2. Step 2: Use two stacks approach

   One stack tracks positions of opening brackets, another tracks positions of '*'. This allows matching '*' as needed to balance brackets efficiently in one pass.

3. Step 3: Reject invalid sequences

   After processing, ensure all unmatched opening brackets can be matched by '*' positions appearing after them.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Two stacks track brackets and wildcards to handle all cases [OK]

Hint: Two stacks track brackets and wildcards for flexible matching [OK]

Common Mistakes:

• Replacing '*' blindly or ignoring them causes incorrect results