Problem Description

You are given a string s consisting of lowercase English letters.

You must repeatedly perform the following operation while the string s has at least two consecutive characters:

• Remove the leftmost pair of adjacent characters in the string that are consecutive in the alphabet, in either order (for example, 'a' and 'b', or 'b' and 'a').
• Shift the remaining characters to the left to fill the gap.

Return the resulting string after no more operations can be performed.

Note: Consider the alphabet as circular, so 'a' and 'z' are also considered consecutive.

Intuition

To simulate the process of removing pairs of consecutive, adjacent characters, think of scanning the string from left to right. Each time you find a pair, you remove them and the string "collapses." This is similar to handling pairs in a stack: for each character, if it forms a valid pair with the character before it (either next to each other in the alphabet or wrapping around between 'a' and 'z'), you remove the previous character (pop from the stack). If not, you just add the current character (push onto the stack). Using a stack helps efficiently keep track of which characters could possibly pair and be removed as you move through the string.

Solution Approach

A stack is used to efficiently simulate the process of removing adjacent consecutive letters. Here is how the algorithm works:

• Start with an empty stack.
• Iterate through each character c in the string s.
  • If the stack is not empty and the character at the top of the stack and c are consecutive (their ASCII values differ by 1 or 25, which covers the wrap-around between 'a' and 'z'), pop the top character from the stack. This removes the leftmost adjacent consecutive pair.
  • Otherwise, push the current character c onto the stack.
• After processing all characters, the stack contains the remaining characters in their original order which could not be removed.
• Combine the stack into a string and return it.

In code, this process looks like:

stk = []
for c in s:
    if stk and abs(ord(c) - ord(stk[-1])) in (1, 25):
        stk.pop()
    else:
        stk.append(c)
return "".join(stk)

This approach works efficiently in a single pass through the string, and the stack structure naturally handles the removal and shifting as required by the problem statement.

Example Walkthrough

Consider the string s = "cabbad". Let's walk through how the stack-based solution processes this string:

1. Start with an empty stack: []

2. Process 'c' Stack is empty, so push 'c': Stack: ['c']

3. Process 'a' Check if 'a' and top of stack ('c') are consecutive:

   • Difference is abs(ord('a') - ord('c')) = 2 (not consecutive), so push 'a': Stack: ['c', 'a']

4. Process 'b' Check if 'b' and top of stack ('a') are consecutive:

   • Difference is 1 (they are consecutive), so pop 'a': Stack: ['c']

5. Process 'b' (the next 'b') Check if 'b' and top of stack ('c') are consecutive:

   • Difference is 1 (they are consecutive), so pop 'c': Stack: []

6. Process 'a' Stack is empty, so push 'a': Stack: ['a']

7. Process 'd' Check if 'd' and top of stack ('a') are consecutive:

   • Difference is 3 (not consecutive), so push 'd': Stack: ['a', 'd']

Result: The stack now contains ['a', 'd']. So, after all removals, the resulting string is "ad".

This example shows how each adjacent pair of consecutive letters gets removed, including the effect of "collapsing" the string as removals happen.

Solution Implementation

Time and Space Complexity

• Time Complexity: O(n) Each character in the string s is processed exactly once. The stack operations (append and pop) each take O(1) time, so the total time is linear with respect to the length of s.

• Space Complexity: O(n) In the worst case, none of the characters are removed, so the stack can contain up to n characters, where n is the length of the input string s.