Scale Engineer

Resulting String After Adjacent Removals

Med
#3171Time: 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).
Data structures
StringStack

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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).

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem