Remove All Adjacent Duplicates In String - Practice Coding Problems

Remove All Adjacent Duplicates In String - Problem

String Stack Easy

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

Input & Output

Example 1 — Basic Case

$ Input: s = "abbaca"

› Output: "ca"

💡 Note: First remove "bb" to get "aaca", then remove "aa" to get "ca". No more adjacent duplicates exist.

Example 2 — Complete Removal

$ Input: s = "azxxzy"

› Output: "ay"

💡 Note: Remove "xx" to get "azzy", then remove "zz" to get "ay". Final result is "ay".

Example 3 — No Duplicates

$ Input: s = "abc"

› Output: "abc"

💡 Note: No adjacent duplicates exist, so the string remains unchanged.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Original string with adjacent duplicates

Process

Remove adjacent duplicate pairs repeatedly

Output

Final string with no adjacent duplicates

Key Takeaway

🎯 Key Insight: Use a stack to efficiently track characters and automatically handle cascading removals when duplicates are found

Asked in

a Amazon 45 M Microsoft 30 G Google 25

The key insight is using a stack to naturally handle adjacent duplicates. When we encounter a character that matches the stack top, we pop (simulating removal of both characters). Otherwise, we push the character. Best approach is the stack method with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Repeated Scanning	O(n²)	O(n)	Repeatedly scan string and remove first adjacent duplicate found
Stack Approach	O(n)	O(n)	Use stack to track characters, pop when duplicate found

Brute Force - Repeated Scanning — Algorithm Steps

Scan string for first adjacent duplicate pair
Remove the pair and rebuild string
Repeat until no duplicates found

Visualization

Tap to expand

Step-by-Step Walkthrough

First Scan

Find first adjacent duplicate

Remove Pair

Remove the duplicate pair

Repeat

Start scanning from beginning again

Code -

solution.c — C

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

char* solution(char* s) {
    int len = strlen(s);
    char* result = (char*)malloc((len + 1) * sizeof(char));
    strcpy(result, s);
    
    while (1) {
        int found = 0;
        char* newS = (char*)malloc((len + 1) * sizeof(char));
        int newIdx = 0;
        int i = 0;
        
        while (i < strlen(result)) {
            if (i + 1 < strlen(result) && result[i] == result[i + 1]) {
                // Skip both characters
                i += 2;
                found = 1;
            } else {
                newS[newIdx++] = result[i];
                i++;
            }
        }
        newS[newIdx] = '\0';
        
        free(result);
        result = newS;
        if (!found) break;
    }
    return result;
}

int main() {
    char s[100001];
    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²)

In worst case, we scan the string O(n) times, each scan takes O(n) time

⚠ Quadratic Growth

Space Complexity

O(n)

Need to create new strings during the removal process

⚡ Linearithmic Space

180.0K Views

Medium Frequency

~15 min Avg. Time

4.2K 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

Brute Force - Repeated Scanning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler