Skip to main content
Talentd

Resulting String After Adjacent Removals - Solution & Explanation

MediumStringStackSimulation7 min readAsked at: Meta
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given a string and repeatedly remove adjacent character pairs that satisfy the removal rule defined in the problem. After no more valid adjacent pairs exist, return the final resulting string.

Approach 1: Repeated String Simulation (Brute Force) (Time: O(n^2), Space: O(n))

The most direct method repeatedly scans the string and removes adjacent pairs whenever they satisfy the removal condition. After each removal, the string shrinks and the scan restarts because new removable pairs may appear. This simulates the process exactly as described. The downside is efficiency: each removal can trigger another full pass over the string, leading to quadratic time in the worst case. This approach is useful for understanding the mechanics of the problem but is rarely acceptable for large inputs.

Approach 2: Stack-Based Simulation (Time: O(n), Space: O(n))

A stack models the removal process efficiently. Iterate through the string once. For each character, compare it with the character at the top of the stack. If the two characters form a removable adjacent pair according to the rule, pop the stack (which simulates removing the pair). Otherwise, push the current character onto the stack. This works because any newly formed adjacency after a removal will automatically be checked with the next incoming character.

The key insight: removals only depend on the most recent unresolved character. A stack preserves exactly that state. Each character is pushed once and popped at most once, giving linear time complexity. This turns what looks like repeated rescanning into a single pass simulation.

After processing the entire string, the stack contains the remaining characters in order. Join them to produce the resulting string. The algorithm processes each character once, making it optimal for large inputs.

This problem is a classic pattern combining string processing with a stack to handle pair cancellations. The same technique appears in problems involving bracket validation, adjacent duplicate removal, and collision simulations.

Recommended for interviews: The stack-based solution is what interviewers expect. The brute force simulation demonstrates that you understand the removal process, but the stack approach shows algorithmic maturity by converting repeated rescans into a single linear pass.

Solution

We can use a stack to simulate the process of removing adjacent characters. Iterate through each character in the string. If the character at the top of the stack and the current character are consecutive (i.e., their ASCII values differ by 1 or 25), pop the top character from the stack; otherwise, push the current character onto the stack. Finally, the characters remaining in the stack are those that can no longer be removed. Join the characters in the stack into a string and return it.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the string.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Repeated String Simulation (Brute Force)O(n^2)O(n)Useful for understanding the removal process or small inputs
Stack-Based SimulationO(n)O(n)Optimal approach for general cases and interview solutions

Video Solution

Q2: Resulting String After Adjacent Removals | LeetCode Java Solution | Weekly Contest 451 • ExpertFunda • 250 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Resulting String After Adjacent Removals easy or hard?
Resulting String After Adjacent Removals is generally classified as a Medium difficulty problem. The logic is straightforward once you recognize the stack pattern, but identifying that repeated removals can be simulated with a single-pass stack requires algorithmic insight.
Resulting String After Adjacent Removals Python/Java solution
The typical implementation uses a stack (or dynamic array) in Python, Java, C++, Go, or TypeScript. Iterate through the string, compare with the stack top, and remove pairs when the rule is satisfied. This produces an O(n) solution that works efficiently for large inputs.
How to solve Resulting String After Adjacent Removals in O(n)?
Process the string from left to right using a stack. For every character, check the top of the stack to see if the pair satisfies the removal rule. If it does, pop the stack to simulate deleting the pair; otherwise push the character. After processing all characters, join the stack contents to produce the final string in O(n) time.
What is the best approach for Resulting String After Adjacent Removals?
The best approach uses a stack to simulate the removal process in a single pass. While iterating through the string, compare the current character with the stack top. If they form a removable adjacent pair, pop the stack; otherwise push the character. This ensures each character is processed at most twice, resulting in O(n) time complexity.
Is Resulting String After Adjacent Removals asked at Google/Amazon/Meta?
Problems involving adjacent pair removals and stack-based string reduction appear frequently in interviews at companies like Google, Amazon, and Meta. Variants include removing adjacent duplicates, bracket validation, and collision simulations, all of which rely on the same stack pattern.
What data structure is used in Resulting String After Adjacent Removals?
A stack is the primary data structure used to solve this problem efficiently. The stack keeps track of unresolved characters and allows constant-time push and pop operations when a removable adjacent pair is detected during the scan.
What is the time complexity of Resulting String After Adjacent Removals?
The optimal stack-based solution runs in O(n) time where n is the length of the string. Each character is pushed onto the stack once and can be popped at most once. The space complexity is also O(n) in the worst case when no removals occur.

Ready to solve this problem?

Practice Resulting String After Adjacent Removals with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring