Remove All Adjacent Duplicates in String II

Remove All Adjacent Duplicates in String II - Problem

String Stack Medium

You are given a string s and an integer k. A k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

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

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

Input & Output

Example 1 — Basic Case

$ Input: s = "abccba", k = 2

› Output: "ccba"

💡 Note: We can remove "ab" leaving "ccba". No more k=2 adjacent duplicates exist.

Example 2 — Multiple Removals

$ Input: s = "abbbaaca", k = 3

› Output: "ca"

💡 Note: First remove "bbb" → "abaaca", then remove "aaa" → "ca". No more k=3 adjacent duplicates.

Example 3 — No Removals

$ Input: s = "aa", k = 3

› Output: "aa"

💡 Note: No groups of 3 consecutive identical characters exist, so string remains unchanged.

Constraints

1 ≤ s.length ≤ 10⁵
2 ≤ k ≤ 10⁴
s only contains lower case English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

String with potential k-duplicate groups

Process

Remove groups of k consecutive identical characters

Output

Final string after all removals

Key Takeaway

🎯 Key Insight: Use a stack to track characters and their consecutive counts for efficient k-duplicate removal

Asked in

F Facebook 45 a Amazon 35 G Google 30 M Microsoft 25

The key insight is to use a stack to track characters and their consecutive counts. When we encounter k consecutive identical characters, we remove them immediately. The stack approach is optimal with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Stack with Character Counting	O(n)	O(n)	Use stack to track characters and their consecutive counts
Brute Force - Repeated String Search	O(n²)	O(1)	Repeatedly scan string to find and remove k consecutive duplicates

Stack with Character Counting — Algorithm Steps

Process each character in the string
If stack top has same character, increment its count
If count reaches k, pop from stack
If different character or empty stack, push new element

Visualization

Tap to expand

Step-by-Step Walkthrough

Process

For each character, check if it matches stack top

Count

Increment count if same, or push new character

Remove

Pop from stack when count reaches k

Code -

solution.c — C

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

typedef struct {
    char ch;
    int count;
} CharCount;

char* solution(char* s, int k) {
    int len = strlen(s);
    CharCount* stack = malloc(len * sizeof(CharCount));
    int stackSize = 0;
    
    for (int i = 0; i < len; i++) {
        char c = s[i];
        if (stackSize > 0 && stack[stackSize - 1].ch == c) {
            stack[stackSize - 1].count++;
            if (stack[stackSize - 1].count == k) {
                stackSize--;
            }
        } else {
            stack[stackSize].ch = c;
            stack[stackSize].count = 1;
            stackSize++;
        }
    }
    
    // Build result string
    char* result = malloc((len + 1) * sizeof(char));
    int resultLen = 0;
    for (int i = 0; i < stackSize; i++) {
        for (int j = 0; j < stack[i].count; j++) {
            result[resultLen++] = stack[i].ch;
        }
    }
    result[resultLen] = '\0';
    
    free(stack);
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string, each character processed at most twice (push and pop)

✓ Linear Growth

Space Complexity

O(n)

Stack can hold up to n elements in worst case when no removals occur

⚡ Linearithmic Space

67.5K Views

Medium Frequency

~15 min Avg. Time

1.9K 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 with Character Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler