MediumStringStackUpdated Sep 2026

1209. Remove All Adjacent Duplicates in String II

Asked at Salesforce

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

String

Companies

1

Problem

You are given a string s and an integer k. A k-duplicate removal means picking k equal letters that sit next to each other in the string and deleting them. After the delete, the part on the left and the part on the right join together, which may create new groups of k equal letters.

Keep doing these removals until no group of k equal adjacent letters is left. Return the final string. The problem guarantees the answer is always the same, no matter which valid group you delete first.

Note that a removal only happens when exactly k equal letters are adjacent, and the letters must be next to each other in the current string — not just somewhere in the original string.

Delete k equal neighbors, then repeat

deeedbbcccbdaa012345678910111213k = 3, so "eee" and "ccc" are the first groups we can delete.ddbbbdaa01234567After the join, "bbb" appears and can be removed next.aa01Removing "ddd" leaves "aa", and no group of 3 remains.
Removing a group joins its two sides, which can create a new group to remove.

Constraints

  • ●1 <= s.length <= 10^5
  • ●2 <= k <= 10^4
  • ●s contains only lowercase English letters

Examples

Example 1
Inputs = "abcd", k = 2
Output"abcd"
WhyNo two equal letters are next to each other, so nothing can be removed and the string stays the same.
Example 2
Inputs = "deeedbbcccbdaa", k = 3
Output"aa"
WhyFirst remove "eee" and "ccc", giving "ddbbbdaa". Now "bbb" is adjacent, so remove it to get "dddaa". Then "ddd" is adjacent, so remove it, leaving "aa".
Example 3
Inputs = "pbbcggttciiippooaais", k = 2
Output"ps"
WhyRemoving pairs step by step (bb, gg, tt, ii, pp, oo, aa, and the ii that forms later) leaves only "ps".

Asked At

1 companies
CompanyDifficulty
SalesforceMediumView all Salesforce questions →

How to Think About It

1

Brute force: scan the string repeatedly and remove k adjacent duplicates until no changes occur.

2

Use a stack to store characters along with their consecutive counts.

3

When pushing a character, check if it matches the top of the stack.

4

If it matches, increment the count at the top; if count reaches k, pop that entry.

5

If it does not match, push the character with count 1 onto the stack.

Optimal Approach

Use a stack where each element stores a character and its consecutive count. Iterate through the string: if the current character equals the top of the stack, increment the count; otherwise push a new entry with count 1. Whenever a count reaches k, pop that entry. After processing the entire string, reconstruct the result by repeating each character in the stack by its count. This runs in O(n) time and O(n) space.

Stack of (letter, run length)

stackd x1e x2← topReading "dee...": 'd' starts a run of 1, then 'e'starts a run of 2.stackd x1e x3← topThe third 'e' makes the top count reach k = 3, so wepop that entry.stackd x2← topThe next 'd' matches the new top, so its count growsto 2 — the two sides have joined.same letter as top: count += 1count == k: pop the entrydifferent letter: push (c, 1)
The stack keeps only the letters that survive so far, each with how many times it repeats in a row.
ComplexityTime O(n)Space O(n)Each character is pushed and popped at most once, and the final string is built in one pass.

What Trips People Up in Real Interviews

1

Clarify whether removals cascade (yes, they do).

2

Mention that a single pass with a stack is optimal.

3

Discuss edge cases: entire string removed, no removals needed.

4

Explain why a naive string-builder approach is O(n*k) worst case.

5

Talk about reconstructing the result from the stack efficiently.

Solution Code

O(n) time
def removeDuplicates(s, k):
    stack = []
    for c in s:
        if stack and stack[-1][0] == c:
            stack[-1][1] += 1
            if stack[-1][1] == k:
                stack.pop()
        else:
            stack.append([c, 1])
    return ''.join(c * cnt for c, cnt in stack)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Remove All Adjacent Duplicates in String II problem?

Given a string s and an integer k, remove k adjacent identical characters repeatedly until no more removals are possible. Return the final string after all possible removals have been performed.

How do you solve Remove All Adjacent Duplicates in String II?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Remove All Adjacent Duplicates in String II?

Remove All Adjacent Duplicates in String II is asked at Salesforce. It is a medium difficulty problem.

What are common mistakes on Remove All Adjacent Duplicates in String II?
  • Clarify whether removals cascade (yes, they do).
  • Mention that a single pass with a stack is optimal.
  • Discuss edge cases: entire string removed, no removals needed.
  • Explain why a naive string-builder approach is O(n*k) worst case.
  • Talk about reconstructing the result from the stack efficiently.