Lexicographically Smallest String After Adjacent Removals

Lexicographically Smallest String After Adjacent Removals - Problem

You are given a string s consisting of lowercase English letters. You can perform the following operation any number of times (including zero):

Remove any 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 lexicographically smallest string that can be obtained after performing the operations optimally.

Note: Consider the alphabet as circular, thus 'a' and 'z' are consecutive.

Input & Output

Example 1 — Consecutive Pairs

$ Input: s = "abdc"

› Output: ""

💡 Note: Remove 'ab' to get "dc", then remove 'dc' to get empty string. Result is lexicographically smallest.

Example 2 — Circular Case

$ Input: s = "azyx"

› Output: "yx"

💡 Note: Remove 'za' (circular consecutive) to get "yx". No more consecutive pairs can be removed.

Example 3 — No Removals

$ Input: s = "aceg"

› Output: "aceg"

💡 Note: No adjacent characters are consecutive, so no pairs can be removed.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

String with potential consecutive adjacent pairs

Process

Remove consecutive pairs optimally using stack

Output

Lexicographically smallest remaining string

Key Takeaway

🎯 Key Insight: Use a stack to greedily remove consecutive pairs as you process the string left to right

Asked in

G Google 45 f Meta 35 a Amazon 30

The key insight is to use a stack for greedy removal of consecutive adjacent pairs. As we process each character, if it forms a consecutive pair with the stack top, we remove both (pop from stack). Otherwise, we add the character to stack. Best approach is the Stack-Based Greedy solution. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Greedy Approach	O(n)	O(n)	Use stack to greedily remove consecutive pairs while building result
Brute Force with Recursion	O(2^n)	O(2^n)	Try all possible removal sequences recursively

Stack-Based Greedy Approach — Algorithm Steps

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

Visualization

Tap to expand

Step-by-Step Walkthrough

Process

Go through each character left to right

Check

If consecutive with stack top, remove pair

Build

Otherwise add to stack

Code -

solution.c — C

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

int isConsecutive(char a, char b) {
    int diff = abs(a - b);
    return diff == 1 || (a == 'a' && b == 'z') || (a == 'z' && b == 'a');
}

char* solution(char* s) {
    int len = strlen(s);
    char* stack = malloc((len + 1) * sizeof(char));
    int top = -1;
    
    for (int i = 0; i < len; i++) {
        if (top >= 0 && isConsecutive(stack[top], s[i])) {
            top--;  // Remove the consecutive pair
        } else {
            stack[++top] = s[i];
        }
    }
    
    stack[top + 1] = '\0';
    return stack;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

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

✓ Linear Growth

Space Complexity

O(n)

Stack can store up to n characters in worst case

⚡ Linearithmic Space

28.5K 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 Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler