Resulting String After Adjacent Removals

MEDIUM

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 (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 <= 10⁵
s consists only of lowercase English letters.

Approaches

Checkout 2 different approaches to solve Resulting String After Adjacent Removals. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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();
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Resulting String After Adjacent Removals. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Resulting String After Adjacent Removals

Data Structures:

StringStack

Resulting String After Adjacent Removals

Description

Approaches

Stack-based Approach

Algorithm

Complexity Analysis

Pros and Cons

Code Solutions

Video Solution

Similar Questions

Data Structures:

On this page

Subscribe to Scale Engineer newsletter