# Resulting String After Adjacent Removals
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/resulting-string-after-adjacent-removals)
Canonical: https://scaleengineer.com/dsa/problems/resulting-string-after-adjacent-removals
**Data structures:** String, Stack
---
## Problem
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 (e.g., `'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, thus `'a'` and `'z'` are consecutive.

**Example 1:**

**Input:** s = "abc"

**Output:** "c"

**Explanation:**

* Remove `"ab"` from the string, leaving `"c"` as the remaining string.
* No further operations are possible. Thus, the resulting string after all possible removals is `"c"`.

**Example 2:**

**Input:** s = "adcb"

**Output:** ""

**Explanation:**

* Remove `"dc"` from the string, leaving `"ab"` as the remaining string.
* Remove `"ab"` from the string, leaving `""` as the remaining string.
* No further operations are possible. Thus, the resulting string after all possible removals is `""`.

**Example 3:**

**Input:** s = "zadb"

**Output:** "db"

**Explanation:**

* Remove `"za"` from the string, leaving `"db"` as the remaining string.
* No further operations are possible. Thus, the resulting string after all possible removals is `"db"`.

**Constraints:**

* `1 <= s.length <= 105`
* `s` consists only of lowercase English letters.

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. It repeatedly scans the string to find the leftmost removable pair, removes it, and then rescans the modified string from the beginning. This continues until no more pairs can be removed.
**Time:** O(N^2), where N is the length of the input string. In the worst case, we might remove only one pair per scan. A single scan and deletion can take up to O(N) time. Since there can be up to O(N) removals, the total time complexity is quadratic. · **Space:** O(N), where N is the length of the input string. This space is used to store the `StringBuilder`.
**Pros:** Simple to understand and implement as it directly follows the problem statement.
**Cons:** Inefficient due to repeated scanning of the string.; Likely to result in a 'Time Limit Exceeded' error for large inputs.
### Explanation
This method directly translates the problem description into code. We use a loop that continues as long as we can find and remove a pair. In each iteration of the loop, we scan the current string from left to right. The first time we find an adjacent, consecutive pair of characters, we remove them. Since this removal might create a new removable pair at an earlier position (e.g., `"adcb"` becomes `"ab"`), we must restart the scan from the beginning of the newly modified string. If we perform a full scan without finding any pairs to remove, the process is complete.

A `StringBuilder` is used for efficient string manipulation, as repeated creation of new `String` objects would be even less performant.

```java
class Solution {
    private boolean areConsecutive(char c1, char c2) {
        int diff = Math.abs(c1 - c2);
        // Check for adjacent letters (e.g., 'a', 'b') or circular ('a', 'z')
        return diff == 1 || diff == 25;
    }

    public String resultingString(String s) {
        StringBuilder sb = new StringBuilder(s);
        boolean pairWasRemoved = true;

        while (pairWasRemoved) {
            pairWasRemoved = false;
            int n = sb.length();
            if (n < 2) {
                break;
            }

            for (int i = 0; i < n - 1; i++) {
                if (areConsecutive(sb.charAt(i), sb.charAt(i + 1))) {
                    sb.delete(i, i + 2);
                    pairWasRemoved = true;
                    break; // Restart scan from the beginning
                }
            }
        }
        return sb.toString();
    }
}
```
### Algorithm
- Initialize a `StringBuilder` with the input string `s`.
- Start a `while` loop that continues as long as a pair is removed in a pass.
- Inside the loop, set a flag `foundPair` to `false`.
- Iterate through the `StringBuilder` from the first character up to the second to last.
- For each index `i`, check if the character at `i` and `i+1` are consecutive.
- If they are, remove the pair from the `StringBuilder`, set `foundPair` to `true`, and `break` the inner loop to restart the scan.
- If the inner loop completes without finding a pair, the `while` loop condition will be false, and the loop terminates.
- Return the final string from the `StringBuilder`.

## Stack-based Approach
A more efficient approach uses a stack-like data structure (like a `StringBuilder` or a `Deque`) to build the result string. We iterate through the input string once. For each character, we compare it with the top of the stack. If they form a removable pair, we pop the stack. Otherwise, we push the current character onto the stack. This avoids the repeated scanning of the brute-force method.
**Time:** O(N), where N is the length of the input string. We iterate through the string only once, and each operation on the `StringBuilder` (append, check last character, delete last character) takes amortized O(1) time. · **Space:** O(N), where N is the length of the input string. The `StringBuilder` can grow up to the size of the input string in the worst case (when no characters are removed).
**Pros:** Highly efficient with linear time complexity.; Solves the problem in a single pass over the input string.
**Cons:** Requires extra space proportional to the input size.
### Explanation
This method processes the string in a single pass, which is much more efficient. The core idea is that a character only needs to be compared with its immediate valid predecessor in the resulting string. A stack is the perfect data structure for this, as it provides easy access to the last-added element (LIFO - Last-In, First-Out).

We can use a `StringBuilder` to function as a character stack. We iterate through each character of the input string. If the `StringBuilder` (our result) is not empty and its last character forms a consecutive pair with the current character, we've found a removable pair. We remove the last character from the `StringBuilder` (a 'pop' operation). Otherwise, the current character cannot be removed, so we append it to the `StringBuilder` (a 'push' operation).

This correctly handles cascading removals (like in `"adcb"`) because after a 'pop', the new last character of the `StringBuilder` is exposed and will be compared against the next character from the input string.

```java
class Solution {
    private boolean areConsecutive(char c1, char c2) {
        int diff = Math.abs(c1 - c2);
        return diff == 1 || diff == 25;
    }

    public String resultingString(String s) {
        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()) {
            int len = result.length();
            if (len > 0 && areConsecutive(result.charAt(len - 1), c)) {
                result.deleteCharAt(len - 1);
            } else {
                result.append(c);
            }
        }
        return result.toString();
    }
}
```
### Algorithm
- Initialize an empty `StringBuilder` to act as a stack.
- Iterate through each character `c` of the input string `s`.
- Check if the `StringBuilder` is not empty.
- If it's not empty, get the last character from the `StringBuilder`.
- Check if the last character and the current character `c` are consecutive.
- If they are, delete the last character from the `StringBuilder`.
- If the `StringBuilder` is empty or the characters are not consecutive, append `c` to the `StringBuilder`.
- After the loop finishes, convert the `StringBuilder` to a string and return it.

# Solutions
### Java

```java
class Solution {
public
  String resultingString(String s) {
    StringBuilder stk = new StringBuilder();
    for (char c : s.toCharArray()) {
      if (stk.length() > 0 && isContiguous(stk.charAt(stk.length() - 1), c)) {
        stk.deleteCharAt(stk.length() - 1);
      } else {
        stk.append(c);
      }
    }
    return stk.toString();
  }
private
  boolean isContiguous(char a, char b) {
    int t = Math.abs(a - b);
    return t == 1 || t == 25;
  }
}

```

### CPP

```cpp
class Solution {
public:
  string resultingString(string s) {
    string stk;
    for (char c : s) {
      if (stk.size() &&
          (abs(stk.back() - c) == 1 || abs(stk.back() - c) == 25)) {
        stk.pop_back();
      } else {
        stk.push_back(c);
      }
    }
    return stk;
  }
};

```

### Python

```python
class Solution:
    def resultingString(self, s: str) -> str: 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)

```