Problem Description

You are given a string s consisting of lowercase English letters. Your task is to repeatedly remove pairs of adjacent characters that are consecutive in the alphabet until no more removals are possible.

The removal process works as follows:

• Find the leftmost pair of adjacent characters in the string that are consecutive in the alphabet (like 'a' and 'b', or 'b' and 'a')
• Remove both characters from the string
• Shift the remaining characters to the left to fill the gap
• Repeat this process until no consecutive adjacent pairs exist

The alphabet is considered circular, meaning 'z' and 'a' are consecutive characters.

For example:

• In the string "abcd", you would remove 'a' and 'b' first (leftmost consecutive pair), leaving "cd". Then remove 'c' and 'd', leaving an empty string "".
• In the string "acb", you would remove 'c' and 'b' (they are consecutive), leaving "a".
• In the string "zab", you would remove 'z' and 'a' (consecutive due to circular property), leaving "b".

The solution uses a stack-based approach where each character is processed sequentially. When a new character would form a consecutive pair with the character at the top of the stack (checking if their ASCII values differ by 1 or 25 for the circular case), both characters are removed by popping the stack. Otherwise, the new character is added to the stack. The final contents of the stack represent the resulting string after all possible removals.

Intuition

The key insight is recognizing that this problem involves matching and removing pairs, which naturally suggests a stack-based approach. When we need to remove adjacent elements based on some condition, a stack is often the ideal data structure because it gives us easy access to the most recent element we've kept.

Think about how the removal process works: we scan from left to right, and whenever we find a consecutive pair, we remove both characters. After removal, the character that was to the left of the removed pair might now form a new consecutive pair with the character that was to the right. This creates a cascading effect of potential removals.

Consider the string "dcba":

• We process 'd', add it to our result
• We process 'c', it forms a consecutive pair with 'd', so we remove both
• We process 'b', add it to our result (nothing to pair with)
• We process 'a', it forms a consecutive pair with 'b', so we remove both
• Final result: empty string

This behavior mirrors exactly how a stack operates. As we traverse the string:

• If the current character and the top of the stack form a consecutive pair, we "undo" the previous addition by popping the stack
• Otherwise, we push the current character onto the stack

The consecutive check is straightforward: two characters are consecutive if their ASCII values differ by exactly 1 (like 'a' and 'b') or by 25 (for the circular case like 'z' and 'a'). Using abs(ord(c) - ord(stk[-1])) gives us the absolute difference, and checking if it equals 1 or 25 covers all consecutive pairs.

This greedy approach of always removing the leftmost consecutive pair first is optimal because removing any consecutive pair can only create at most one new consecutive pair (between the characters that were separated by the removed pair), so the order of removal doesn't affect the final result.

Learn more about Stack patterns.

Solution Approach

The solution uses a stack to simulate the removal process efficiently. Here's how the implementation works:

Data Structure: We use a stack (implemented as a Python list) to keep track of characters that haven't been removed yet.

Algorithm Steps:

1. Initialize an empty stack stk = [] to store characters that remain after removals.

2. Iterate through each character in the string s:

   for c in s:

3. Check for consecutive pair formation:

   • First, verify the stack is not empty: if stk
   • Calculate the absolute difference between ASCII values of the current character and the top of the stack: abs(ord(c) - ord(stk[-1]))
   • Check if this difference equals 1 or 25:
     • Difference of 1 means regular consecutive characters (like 'a' and 'b')
     • Difference of 25 handles the circular case (like 'z' and 'a')

4. Perform the appropriate action:

   • If a consecutive pair is found: stk.pop() removes the top character from the stack, effectively removing both characters from consideration
   • If no consecutive pair: stk.append(c) adds the current character to the stack

5. Build the result: After processing all characters, join the remaining characters in the stack to form the final string:

   return "".join(stk)

Why this works:

• The stack naturally maintains the order of characters from left to right
• When we find a consecutive pair, popping from the stack removes the left character of the pair, and not adding the current character removes the right character
• The process automatically handles cascading removals because after each pop operation, the new top of the stack is checked against the next character

Time Complexity: O(n) where n is the length of the string, as each character is pushed and popped at most once.

Space Complexity: O(n) in the worst case when no characters can be removed, requiring the stack to store all characters.

Example Walkthrough

Let's walk through the string "cabdz" step by step to illustrate how the stack-based solution works:

Initial state:

• String: "cabdz"
• Stack: []

Step 1: Process 'c'

• Stack is empty, so add 'c'
• Stack: ['c']

Step 2: Process 'a'

• Check if 'a' and 'c' (top of stack) are consecutive
• abs(ord('a') - ord('c')) = abs(97 - 99) = 2
• Not consecutive (not 1 or 25), so add 'a'
• Stack: ['c', 'a']

Step 3: Process 'b'

• Check if 'b' and 'a' (top of stack) are consecutive
• abs(ord('b') - ord('a')) = abs(98 - 97) = 1
• They ARE consecutive! Pop 'a' from stack (removing the pair 'a' and 'b')
• Stack: ['c']

Step 4: Process 'd'

• Check if 'd' and 'c' (top of stack) are consecutive
• abs(ord('d') - ord('c')) = abs(100 - 99) = 1
• They ARE consecutive! Pop 'c' from stack (removing the pair 'c' and 'd')
• Stack: []

Step 5: Process 'z'

• Stack is empty, so add 'z'
• Stack: ['z']

Final Result:

• Join the stack contents: "z"

This example demonstrates:

• How the stack maintains characters that haven't been removed
• The cascading effect: removing 'a' and 'b' exposed 'c' to pair with 'd'
• How consecutive pairs are detected using ASCII value differences
• The final string contains only characters that couldn't form consecutive pairs

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the string s once, where n is the length of the string. For each character, it performs constant-time operations:

• Checking if the stack is non-empty: O(1)
• Computing the absolute difference between ASCII values: O(1)
• Checking if the difference is 1 or 25: O(1)
• Either popping from or appending to the stack: O(1)

Since we perform O(1) operations for each of the n characters, the overall time complexity is O(n).

Space Complexity: O(n)

The space complexity is determined by the stack stk which stores characters from the input string. In the worst case, when no characters are removed (no adjacent characters have ASCII differences of 1 or 25), the stack will contain all n characters from the input string. Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting the Circular Nature of the Alphabet

The Pitfall: Many developers initially implement the solution checking only for abs(ord(char) - ord(stack[-1])) == 1, forgetting that 'z' and 'a' are also consecutive characters in a circular alphabet. This leads to incorrect results when the string contains 'z' and 'a' pairs.

Example of Incorrect Code:

# WRONG - doesn't handle circular case
if stack and abs(ord(char) - ord(stack[-1])) == 1:
    stack.pop()

The Solution: Always check for both differences of 1 and 25:

# CORRECT - handles both regular and circular cases
if stack and abs(ord(char) - ord(stack[-1])) in (1, 25):
    stack.pop()

2. Misunderstanding Order of Operations

The Pitfall: Some might think they need to find ALL consecutive pairs first, then remove them simultaneously. This leads to complex logic trying to mark or track multiple pairs.

Example of Overthinking:

# WRONG - trying to find all pairs first
pairs_to_remove = []
for i in range(len(s) - 1):
    if are_consecutive(s[i], s[i+1]):
        pairs_to_remove.append(i)
# Then trying to remove them... gets complicated!

The Solution: Process characters sequentially from left to right. The stack approach naturally handles cascading removals:

# CORRECT - process one character at a time
for char in s:
    if stack and abs(ord(char) - ord(stack[-1])) in (1, 25):
        stack.pop()  # Immediate removal
    else:
        stack.append(char)

3. Not Checking if Stack is Empty Before Accessing Top

The Pitfall: Attempting to access stack[-1] when the stack is empty causes an IndexError.

Example of Bug:

# WRONG - will crash if stack is empty
for char in s:
    if abs(ord(char) - ord(stack[-1])) in (1, 25):  # IndexError if stack is empty!
        stack.pop()

The Solution: Always check if the stack has elements before accessing the top:

# CORRECT - checks stack is not empty first
for char in s:
    if stack and abs(ord(char) - ord(stack[-1])) in (1, 25):
        stack.pop()

4. Using String Concatenation Instead of Stack

The Pitfall: Building the result string by repeatedly concatenating or slicing strings is inefficient and makes the logic more complex.

Example of Inefficient Approach:

# INEFFICIENT - string operations are O(n) each
result = ""
for char in s:
    if result and are_consecutive(result[-1], char):
        result = result[:-1]  # O(n) operation
    else:
        result += char  # Can be O(n) in some implementations

The Solution: Use a list/stack and join at the end for O(n) total complexity:

# EFFICIENT - O(1) stack operations
stack = []
for char in s:
    # ... stack operations ...
return "".join(stack)  # Single O(n) operation at the end