Resulting String After Adjacent Removals - Practice Coding Problems

Resulting String After Adjacent Removals - 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.

Input & Output

Example 1 — Basic Removal

$ Input: s = "cabd"

› Output: "cd"

💡 Note: First we find the consecutive pair 'a' and 'b' at positions 1,2. After removing them, we get 'cd' with no more consecutive pairs.

Example 2 — Multiple Removals

$ Input: s = "dcba"

› Output: ""

💡 Note: Remove 'cb' → 'da', then remove 'da' (circular: 'd' and 'a' are consecutive) → empty string.

Example 3 — Circular Case

$ Input: s = "za"

› Output: ""

💡 Note: Since the alphabet is circular, 'z' and 'a' are consecutive, so they form a removable pair.

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String with consecutive letter pairs like 'ab', 'zy'

Process

Remove leftmost consecutive pairs repeatedly

Output

Final string with no consecutive pairs

Key Takeaway

🎯 Key Insight: Use a stack to efficiently track and remove consecutive pairs in a single pass

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

The key insight is to use a stack to process characters sequentially, removing consecutive pairs as we encounter them. The stack approach is optimal with O(n) time and O(n) space complexity, efficiently handling the leftmost pair requirement.

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Approach	O(n)	O(n)	Use stack to build result string, popping when consecutive pairs are found
Brute Force - Repeated Scanning	O(n²)	O(1)	Repeatedly scan string from left to right, removing consecutive pairs until no more pairs exist

Stack-Based Approach — Algorithm Steps

Initialize empty stack
For each character, check if it's consecutive with stack top
If consecutive, pop stack; otherwise push character
Return stack contents as final string

Visualization

Tap to expand

Step-by-Step Walkthrough

Process 'c'

Stack empty, push 'c'

Process 'a'

Not consecutive with 'c', push 'a'

Process 'b'

Consecutive with 'a', pop 'a' (remove pair)

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool areConsecutive(char a, char b) {
    return (b - a + 26) % 26 == 1 || (a - b + 26) % 26 == 1;
}

void solution(char* s, char* result) {
    char stack[1001];
    int top = -1;
    
    for (int i = 0; s[i]; i++) {
        if (top >= 0 && areConsecutive(stack[top], s[i])) {
            top--;
        } else {
            stack[++top] = s[i];
        }
    }
    
    for (int i = 0; i <= top; i++) {
        result[i] = stack[i];
    }
    result[top + 1] = '\0';
}

int main() {
    char s[1001];
    char result[1001];
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    solution(s, result);
    printf("%s\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string, each character pushed and popped at most once

✓ Linear Growth

Space Complexity

O(n)

Stack can contain up to n characters in worst case when no pairs are found

⚡ Linearithmic Space

24.9K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler