LeetCode 3561 - Resulting String After Adjacent Removals

Difficulty: 🟡 Medium
Topics: String, Stack, Simulation

Solution

Problem Understanding

The problem asks us to repeatedly remove pairs of adjacent characters in a string that are consecutive in the alphabet, considering the alphabet as circular. "Consecutive in the alphabet" means two characters where the difference in their positions in the alphabet is 1, either forwards or backwards, and 'a' and 'z' are also considered consecutive. The operation removes the leftmost such pair first and continues until no more pairs exist. The input is a string s of lowercase letters, with a length up to 10^5. The output is the remaining string after performing all valid removals.

Important points include that we must always remove the leftmost valid pair and that the alphabet is circular. Edge cases that could break a naive solution include strings with repeated patterns, strings that reduce completely to empty, strings with non-consecutive letters, and strings where the circular adjacency ('a' and 'z') matters.

Approaches

The brute-force approach iterates over the string repeatedly, scanning for the first adjacent pair that is consecutive in the alphabet. Once found, it removes the pair and shifts the remaining characters. This continues until no more pairs exist. While this approach is simple and correct, its time complexity is potentially O(n^2) in the worst case because each removal involves scanning potentially the entire string and performing a removal, which is expensive for strings up to 10^5 characters.

The optimal approach uses a stack to simulate the process efficiently. By iterating through the string and maintaining a stack of characters, we can compare the current character with the top of the stack. If the two are consecutive, we pop from the stack, simulating removal. Otherwise, we push the current character onto the stack. This method ensures each character is processed at most twice (once pushed, once potentially popped), yielding an O(n) time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Iteratively scan and remove leftmost valid pair until no more removals
Optimal	O(n)	O(n)	Use a stack to simulate removals in a single pass

Algorithm Walkthrough

Initialize an empty stack to hold characters that have not yet been removed.
Iterate over each character c in the input string s.
If the stack is not empty, compare c with the character at the top of the stack top. Check if the two are consecutive in the alphabet. Two characters x and y are consecutive if abs(ord(x) - ord(y)) == 1 or if (x, y) is the circular pair ('a', 'z') or ('z', 'a').
If the characters are consecutive, pop the top of the stack (this simulates removing the leftmost consecutive pair). The current character is also removed, so do not push it.
If the characters are not consecutive, push c onto the stack.
After processing all characters, join the stack into a string. This represents the resulting string after all possible removals.

Why it works: The stack ensures that we always consider the leftmost possible consecutive pair because each character is compared to its immediate left neighbor (top of the stack). This faithfully simulates the repeated leftmost removal operation efficiently. The problem requires us to process a string s consisting of lowercase English letters and repeatedly remove adjacent pairs of characters that are consecutive in the alphabet. The consecutive rule is bidirectional, meaning both increasing (e.g., 'a' followed by 'b') and decreasing (e.g., 'b' followed by 'a') sequences are valid. Additionally, the alphabet is considered circular, so 'a' and 'z' are also consecutive.

The input string s is between 1 and 105 characters long, which is significant because it rules out naive solutions that repeatedly scan the string in O(n²) time. The output is the resulting string after no more valid adjacent removals can occur.

Important edge cases include strings of length 1 (no removals possible), strings where all characters can be removed in pairs, and strings where only circular pairs like 'az' or 'za' exist. The problem guarantees that the string consists only of lowercase letters, so we do not need to handle invalid characters.

The challenge is to efficiently track which characters to remove and ensure that removal propagates correctly to newly formed consecutive pairs, without repeatedly scanning the string from scratch.

Approaches

The brute-force approach involves scanning the string from left to right and removing the first valid adjacent consecutive pair. After each removal, the scan starts over from the beginning of the string. This ensures correctness because the problem explicitly asks for the leftmost pair removal. However, if the string is long, repeated rescans could lead to O(n²) time complexity, which is too slow for the upper limit of 105 characters.

The key observation for an optimal solution is that the problem can be reduced to a stack simulation. By iterating through the string once and maintaining a stack of characters that have not yet been removed, we can check whether the current character forms a consecutive pair with the character at the top of the stack. If it does, we pop the stack (effectively removing the leftmost pair in a single pass). This approach avoids rescanning the entire string repeatedly and guarantees O(n) time complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly scan the string and remove the first valid pair until no more exist
Optimal	O(n)	O(n)	Use a stack to simulate removals efficiently in a single pass

Algorithm Walkthrough

Initialize an empty stack to keep track of characters that are still in the resulting string.
Iterate over each character in the input string s.
For the current character, check if the stack is non-empty. If it is, compare the current character with the character at the top of the stack to see if they are consecutive alphabetically. Consider circular consecutive pairs ('a' and 'z') as valid.
If the top of the stack and the current character form a consecutive pair, pop the stack. This simulates the removal of the leftmost consecutive pair and automatically shifts remaining characters left.
If they do not form a consecutive pair, push the current character onto the stack.
After iterating through the string, convert the stack back into a string and return it.

Why it works: The stack always contains the current state of the string after all leftmost removals up to the current character. By checking only the top of the stack, we efficiently remove pairs in the correct order, while the stack structure inherently handles propagation of new consecutive pairs after each removal.

Python Solution

class Solution:
    def resultingString(self, s: str) -> str:
        stack = []
        for c in s:
            if stack:
                top = stack[-1]
                if abs(ord(c) - ord(top)) == 1 or (c == 'a' and top == 'z') or (c == 'z' and top == 'a'):
                    stack.pop()
                    continue
            stack.append(c)
        return ''.join(stack)

Explanation: We maintain a stack of characters that have not yet been removed. For each new character, we check if it forms a consecutive pair with the top of the stack, considering the circular alphabet case. If it does, we remove the top of the stack and skip pushing the current character, effectively removing the pair. At the end, joining the stack produces the final string. for char in s: if stack: top = stack[-1] # Check for consecutive characters including circular wrap-around if abs(ord(char) - ord(top)) == 1 or {char, top} == {'a', 'z'}: stack.pop() continue stack.append(char) return ''.join(stack)


The solution iterates through the string and maintains a stack to efficiently remove consecutive pairs. The condition `abs(ord(char) - ord(top)) == 1` checks for standard consecutive characters, while the set comparison `{char, top} == {'a', 'z'}` handles the circular case. Characters that do not form a pair are pushed onto the stack, preserving the correct sequence.

## Go Solution

```go
func resultingString(s string) string {
    stack := []byte{}
    for i := 0; i < len(s); i++ {
        c := s[i]
        if len(stack) > 0 {
            top := stack[len(stack)-1]
            if (c > top && c-top == 1) || (top > c && top-c == 1) || (c == 'a' && top == 'z') || (c == 'z' && top == 'a') {
    stack := []rune{}
    for _, char := range s {
        if len(stack) > 0 {
            top := stack[len(stack)-1]
            if (char-top == 1 || top-char == 1) || (char == 'a' && top == 'z') || (char == 'z' && top == 'a') {
                stack = stack[:len(stack)-1]
                continue
            }
        }
        stack = append(stack, c)
        stack = append(stack, char)
    }
    return string(stack)
}

Explanation: The Go version uses a slice of bytes as a stack. The logic is identical to Python. Go requires careful handling of slice indexing when popping elements. The circular alphabet condition is explicitly checked as in Python.

Worked Examples

Example 1: `s = "abc"`

In Go, we use a slice of runes to correctly handle characters. The logic for consecutive pairs mirrors the Python version, and we handle circular wrap-around explicitly. Appending and slicing the stack in Go simulates pushing and popping efficiently.

Worked Examples

Example 1: s = "abc"

Step	Stack	Action
'a'	['a']	Push 'a'
'b'	[]	'b' and 'a' are consecutive → pop 'a' and skip 'b'
'c'	['c']	Push 'c'

Result: "c"

Example 2: `s = "adcb"`

| 'b' | [] | 'b' forms consecutive pair with 'a', pop 'a' | | 'c' | ['c'] | Push 'c' |

Output: "c"

Example 2: s = "adcb"

Step	Stack	Action
'a'	['a']	Push 'a'
'd'	['a','d']	Not consecutive → push 'd'
'c'	['a']	'c' and 'd' consecutive → pop 'd', skip 'c'
'b'	[]	'b' and 'a' consecutive → pop 'a', skip 'b'

Result: ""

Example 3: `s = "zadb"`

| 'd' | ['a', 'd'] | Push 'd' | | 'c' | ['a'] | 'c' forms consecutive pair with 'd', pop 'd' | | 'b' | [] | 'b' forms consecutive pair with 'a', pop 'a' |

Output: ""

Example 3: s = "zadb"

Step	Stack	Action
'z'	['z']	Push 'z'
'a'	[]	'a' and 'z' are consecutive → pop 'z', skip 'a'
'd'	['d']	Push 'd'
'b'	['d','b']	Not consecutive → push 'b'

Result: "db" | 'a' | [] | 'a' forms circular consecutive pair with 'z', pop 'z' | | 'd' | ['d'] | Push 'd' | | 'b' | ['d', 'b'] | 'b' not consecutive with 'd', push 'b' |

Output: "db"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is pushed and popped at most once
Space	O(n)	Stack may contain all characters in worst case

The stack-based approach ensures linear time since no character is examined more than twice, and space is proportional to the number of characters that remain after all removals. | Time | O(n) | Each character is pushed and popped at most once in the stack, so linear time relative to string length | | Space | O(n) | The stack can hold all characters in the worst case, linear space |

The reasoning is that the stack ensures no character is processed more than twice (once pushed, once popped), avoiding repeated rescans.

Test Cases

# Provided examples
assert Solution().resultingString("abc") == "c"  # Simple removal
assert Solution().resultingString("adcb") == ""  # Multiple sequential removals
assert Solution().resultingString("zadb") == "db"  # Circular adjacency

# Edge and stress tests
assert Solution().resultingString("a") == "a"  # Single character, nothing removed
assert Solution().resultingString("ab") == ""  # Single pair removed
assert Solution().resultingString("za") == ""  # Circular pair removed
assert Solution().resultingString("abcdedcba") == ""  # Nested consecutive removals
assert Solution().resultingString("azbycxdwevfugthsirjqkplomn") == ""  # Full alphabet zigzag removal
assert Solution().resultingString("abc") == "c"  # basic consecutive removal
assert Solution().resultingString("adcb") == ""  # multiple cascading removals
assert Solution().resultingString("zadb") == "db"  # circular consecutive pair

# Boundary cases
assert Solution().resultingString("a") == "a"  # single character, no removal
assert Solution().resultingString("ab") == ""  # full removal of a small pair
assert Solution().resultingString("za") == ""  # circular pair removal

# Stress case
assert Solution().resultingString("abcd" * 25000) == "d" * 25000  # long repetitive pattern

Test	Why
`"abc"`	Tests simple consecutive removal
`"adcb"`	Tests sequential multiple removals
`"zadb"`	Tests circular adjacency
`"a"`	Tests single character
`"ab"`	Tests direct removal of a single pair
`"za"`	Tests circular pair removal
`"abcdedcba"`	Tests nested removal propagation
`"azbycxdwevfugthsirjqkplomn"`	Tests large zigzag full removal

Edge Cases

Single-character string: Since no adjacent pairs exist, the string should remain unchanged. The implementation naturally handles this because the stack will simply contain the single character.
Circular adjacency ('a' and 'z'): Special handling is needed to detect 'a' next to 'z' as consecutive. Both Python and Go solutions explicitly check for these cases.
Nested removals: Removing a pair may create a new consecutive pair with the preceding character. The stack automatically handles this because after a pop, the next iteration considers the new top of the stack, effectively propagating removals.

Edge Cases

One edge case is a string with a single character, e.g., "a". No removal is possible because the operation requires at least two characters. The implementation correctly returns the original character since the stack simply appends it.

Another edge case is a string that consists entirely of consecutive pairs, like "ab", "yz", or "az". Here, every character may be removed. The stack handles this by pushing the first character and popping whenever a consecutive character is encountered, resulting in an empty string if all pairs are removed.

A third edge case involves circular wrap-around, such as "za" or "az". These require special handling because the alphabetical difference is not 1 in terms of ASCII values. By explicitly checking for the set {'a','z'} in Python or the equivalent condition in Go, the implementation ensures circular adjacency is correctly recognized and removed.

LeetCode 3561 - Resulting String After Adjacent Removals

Solution

Problem Understanding

Approaches

Algorithm Walkthrough

Approaches

Algorithm Walkthrough

Python Solution

Worked Examples

Example 1: s = "abc"

Worked Examples

Example 2: s = "adcb"

Example 3: s = "zadb"

Complexity Analysis

Test Cases

Edge Cases

Edge Cases

Example 1: `s = "abc"`

Example 2: `s = "adcb"`

Example 3: `s = "zadb"`