Resulting String After Adjacent Removals

medium string stack simulation

Problem

Given a string s of lowercase letters, repeatedly remove the leftmost adjacent pair that is consecutive in the alphabet (either order, e.g. 'a','b' or 'b','a'), shifting the rest left to close the gap. The alphabet is circular, so 'a' and 'z' are also consecutive. Return the string once no more removals are possible.

Inputs = "abc"

Output"c"

Remove "ab" (a and b are consecutive), leaving "c". No pair remains, so the answer is "c".

s (lowercase letters)

def resultingString(s):
    stack = []
    for ch in s:
        if stack:
            diff = abs(ord(stack[-1]) - ord(ch))
            # consecutive in the circular alphabet?
            if diff == 1 or diff == 25:
                stack.pop()          # cancel the pair
                continue
        stack.append(ch)             # otherwise keep ch
    return "".join(stack)

function resultingString(s) {
  const stack = [];
  for (const ch of s) {
    if (stack.length) {
      const diff = Math.abs(
        stack[stack.length - 1].charCodeAt(0) - ch.charCodeAt(0));
      // consecutive in the circular alphabet?
      if (diff === 1 || diff === 25) {
        stack.pop();                 // cancel the pair
        continue;
      }
    }
    stack.push(ch);                  // otherwise keep ch
  }
  return stack.join("");
}

String resultingString(String s) {
    StringBuilder stack = new StringBuilder();
    for (char ch : s.toCharArray()) {
        int n = stack.length();
        if (n > 0) {
            int diff = Math.abs(stack.charAt(n - 1) - ch);
            // consecutive in the circular alphabet?
            if (diff == 1 || diff == 25) {
                stack.deleteCharAt(n - 1);   // cancel the pair
                continue;
            }
        }
        stack.append(ch);                    // otherwise keep ch
    }
    return stack.toString();
}

string resultingString(string s) {
    string stack;
    for (char ch : s) {
        if (!stack.empty()) {
            int diff = abs(stack.back() - ch);
            // consecutive in the circular alphabet?
            if (diff == 1 || diff == 25) {
                stack.pop_back();    // cancel the pair
                continue;
            }
        }
        stack.push_back(ch);         // otherwise keep ch
    }
    return stack;
}

Explanation

Although the problem talks about deleting the leftmost pair again and again and shifting everything left, that repeated rescanning is exactly what a stack does in a single left-to-right pass.

Scan the string one character at a time. Keep a stack of the characters that have survived so far. For each new character ch, look at the top of the stack: if those two letters are consecutive in the alphabet, they form a removable pair, so we pop the top and drop ch too — both vanish. Otherwise ch has no partner yet, so we push it.

Why does this match "remove the leftmost pair repeatedly"? Because once a pair cancels, the character now exposed on top of the stack is precisely the one that becomes newly adjacent to the rest — the same character a left-shift would bring next to it. The stack top always represents the current left neighbour, so popping reproduces the cascading removals automatically.

The circular adjacency test is simple arithmetic on character codes: two letters are consecutive when the absolute difference of their codes is 1 (like 'a','b') or 25 (the wrap-around case 'a','z').

Example: s = "adcb". Push a, push d; c cancels d (diff 1); then b cancels the exposed a (diff 1). The stack empties, so the answer is the empty string.

Time: O(n) Space: O(n)