1047. Remove All Adjacent Duplicates In String

, ,

Idea

Use a stack to keep track of characters.

Code

“Real” Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string removeDuplicates(string s) {
        string ans = "";
        for(char c: s){
            if(!ans.empty() && ans.back() == c){
                ans.pop_back();
            }
            else{
                ans.push_back(c);
            }
        }
        return ans;
    }
    
};

Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string removeDuplicates(string s) {
        int i = 0;
        for(int j = 0; j < s.length(); j++, i++){
            s[i] = s[j];
            if(i > 0 && s[i] == s[i - 1]){
                i -= 2;
            }
        }
        return s.substr(0, i);
    }
    
};

(explained by ChatGPT)

Instead of a stack data structure, it reuses the string s itself as the stack.

Variables:

  • j = the read index (iterate through the original string, left to right).
  • i = the write index (the “top of stack” inside s).

The loop

1
2
3
4
5
for (int j = 0; j < n; ++j, ++i) {
    s[i] = s[j];               // push s[j] onto the "stack" at position i
    if (i > 0 && s[i - 1] == s[i]) // top two are duplicates?
        i -= 2;                 // "pop" both
}
  • s[i] = s[j] → copies the current char onto the “stack”.
  • Then it checks: if the top two (s[i] and s[i-1]) are equal → we undo both by setting i -= 2.

So i always points to where the next character should be written.
At the end, s.substr(0, i) returns the “stack contents”.

Why it works

  • Every char is processed exactly once (j goes 0..n-1).

  • Each char is either:

    • kept (written at position i), or
    • canceled out with its duplicate (via i -= 2).

  • The logic of i -= 2 ensures that when duplicates are removed, the stack shrinks by 2, just like popping from a real stack.

Thus this algorithm simulates the push-pop behavior of a stack, but in place, with O(1) extra memory.

Quick dry run

s = "abbaca"

  • j=0: s[0]='a', push → stack = "a" (i=1)
  • j=1: s[1]='b', push → "ab" (i=2)
  • j=2: s[2]='b', push → "abb" → dup! → pop → "a" (i=1)
  • j=3: s[3]='a', push → "aa" → dup! → pop → "" (i=0)
  • j=4: s[4]='c', push → "c" (i=1)
  • j=5: s[5]='a', push → "ca" (i=2)

Result = s.substr(0,2) = "ca" ✅

Summary

This works because:

  • i serves as a simulated stack pointer.
  • s[i] = s[j] is like “pushing” the char.
  • i -= 2 is like “popping” two chars when a duplicate is found.
  • The final prefix of s up to i is the answer.

So it’s a stack algorithm implemented in-place.

Failed Attempt (use recursion)

recursion is having MLE issue

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string removeDuplicates(string s) {
        if(s == "") return s;
        for(int i = 0; i < s.length() - 1; i++){
            if(s[i] == s[i + 1]){
                string ss = s.substr(0, i) + s.substr(i + 2);
                return removeDuplicates(ss);
            }
        }
        return s;
    }
};