# Remove All Adjacent Duplicates In String
**Difficulty:** EASY
[External](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string)
Canonical: https://scaleengineer.com/dsa/problems/remove-all-adjacent-duplicates-in-string
**Data structures:** String, Stack
**Companies:** [Paytm](https://scaleengineer.com/companies/paytm), [Zoho](https://scaleengineer.com/companies/zoho), [Geico](https://scaleengineer.com/companies/geico), [Grammarly](https://scaleengineer.com/companies/grammarly), [Whatnot](https://scaleengineer.com/companies/whatnot)
---
## Problem
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**.

**Example 1:**

**Input:** s = "abbaca"
**Output:** "ca"
**Explanation:** 
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move.  The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

**Example 2:**

**Input:** s = "azxxzy"
**Output:** "ay"

**Constraints:**

* `1 <= s.length <= 105`
* `s` consists of lowercase English letters.

# Approaches
## Brute-Force with Repeated Scans
This approach directly simulates the process described in the problem. It repeatedly scans the string, finds the first pair of adjacent duplicates, removes them, and then starts the scan over from the beginning of the new, shorter string. This continues until a full pass over the string reveals no adjacent duplicates.
**Time:** O(N^2), where N is the length of the string. In the worst-case scenario (e.g., 'abccba'), each removal operation can take O(N) time due to scanning and string/StringBuilder modification. Since there can be up to N/2 removal operations, the total time complexity is quadratic. · **Space:** O(N). In Java, a `StringBuilder` is used to make the string mutable, which requires O(N) space. If using immutable strings, each modification would create a new string, also leading to O(N) space usage for the intermediate strings.
**Pros:** The logic is straightforward and directly follows the problem statement.
**Cons:** Extremely inefficient due to repeated scanning and string manipulations.; Likely to fail on larger test cases due to exceeding the time limit.
### Explanation
This method uses a loop that continues as long as it can find and remove a pair of adjacent, identical characters. Inside the loop, it iterates through the string to find the first such pair. Upon finding one, it removes the pair, effectively shortening the string, and then breaks the inner loop to restart the scan from the beginning of the modified string. This process is guaranteed to terminate because the string's length decreases with each successful removal. While simple to conceptualize, the repeated creation of new string objects (or manipulation of a `StringBuilder` from the start) makes it very slow.

```java
class Solution {
    public String removeDuplicates(String s) {
        StringBuilder sb = new StringBuilder(s);
        boolean found = true;
        while (found) {
            found = false;
            for (int i = 0; i < sb.length() - 1; i++) {
                if (sb.charAt(i) == sb.charAt(i + 1)) {
                    sb.delete(i, i + 2);
                    found = true;
                    break; // Restart scan from the beginning
                }
            }
        }
        return sb.toString();
    }
}
```
### Algorithm
- Start with the input string `s`.
- Enter a loop that continues as long as modifications are being made to the string.
- In each iteration of the loop, find the index `i` of the first occurrence where `s[i] == s[i+1]`.
- If such a pair is found, create a new string by removing the characters at indices `i` and `i+1`. Update `s` to this new string and restart the scan from the beginning.
- If a full scan of the string is completed and no adjacent duplicates are found, exit the loop.
- The final string `s` is the result.

## Using a Stack
A more efficient approach utilizes a stack. The Last-In, First-Out (LIFO) nature of a stack is perfect for this problem. We can iterate through the string, and for each character, we compare it with the character at the top of the stack. If they match, it means we've found an adjacent duplicate pair (one from the past, one current), so we pop the stack. Otherwise, we push the current character onto the stack.
**Time:** O(N), where N is the length of the string. We perform a single pass through the input string. Each character is pushed onto the stack at most once and popped at most once. Stack operations (push, pop, peek) take amortized O(1) time. · **Space:** O(N). In the worst-case scenario, where the string has no adjacent duplicates (e.g., 'abcdef'), the stack will grow to size N, storing all characters of the string.
**Pros:** Optimal time complexity with a single pass.; The logic is clean and effectively solves the problem.
**Cons:** Requires O(N) auxiliary space for the stack.
### Explanation
By processing the string one character at a time, we can decide whether to keep the character or not. A stack is the ideal data structure for this. When we encounter a new character, we look at the top of the stack. If the stack is empty or the top character is different, the new character cannot form a duplicate pair with the preceding character in the result, so we push it onto the stack. If the top character is the same, we have found a pair to remove, which is accomplished by simply popping the stack and not pushing the new character. After one pass, the stack contains the characters of the final string, but in reverse order of construction. We can then build the result string by reading the stack's contents from bottom to top.

```java
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.Iterator;

class Solution {
    public String removeDuplicates(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        StringBuilder result = new StringBuilder();
        // Use a descending iterator to read from bottom to top of the stack
        Iterator<Character> iterator = stack.descendingIterator();
        while (iterator.hasNext()) {
            result.append(iterator.next());
        }
        return result.toString();
    }
}
```
### Algorithm
- Initialize an empty stack. A `Deque` implementation like `ArrayDeque` is a good choice in Java.
- Iterate through each character `c` of the input string `s`.
- If the stack is not empty and the character at the top of the stack (`stack.peek()`) is the same as the current character `c`, pop the character from the stack.
- Otherwise, push the current character `c` onto the stack.
- After iterating through the entire string, the characters in the stack, when read from bottom to top, form the result string.
- Build the final string from the characters remaining in the stack and return it.

## Two Pointers / StringBuilder Optimization
This approach is a highly optimized version of the stack-based solution and is often the most idiomatic way to solve this in Java. Instead of using a formal `Stack` object, we use a `StringBuilder` which acts as a character stack. The end of the `StringBuilder` represents the top of the stack. This avoids the overhead of the `Stack` class and boxing/unboxing characters.
**Time:** O(N), where N is the length of the string. We iterate through the string once. `StringBuilder` operations like `append` and `deleteCharAt` at the end take amortized O(1) time. · **Space:** O(N). The `StringBuilder` can grow up to the size of the input string N in the worst case (no duplicates).
**Pros:** Optimal O(N) time complexity.; Generally faster in practice than using the `Stack` class in Java due to less overhead.; Code is concise and clear.
**Cons:** Still requires O(N) auxiliary space, which is unavoidable for this problem in Java since strings are immutable.
### Explanation
This method is conceptually identical to the stack approach but uses a `StringBuilder` for a more direct and often faster implementation in Java. The `StringBuilder` acts as our result string that we build progressively. As we iterate through the input string, we look at the last character added to our `StringBuilder`. If it matches the current character from the input, we remove that last character. If it doesn't match (or if the `StringBuilder` is empty), we append the current character. This perfectly mimics the push/pop logic of a stack using `append` and `deleteCharAt`.

This is also equivalent to a two-pointer approach. One pointer (`i`) iterates through the input string, and another pointer (`sb.length()`) tracks the end of the valid, processed result.

```java
class Solution {
    public String removeDuplicates(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            int len = sb.length();
            if (len > 0 && sb.charAt(len - 1) == c) {
                sb.deleteCharAt(len - 1);
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}
```
### Algorithm
- Initialize an empty `StringBuilder` which will hold the result.
- Iterate through each character `c` of the input string `s`.
- Let `len` be the current length of the `StringBuilder`.
- If the `StringBuilder` is not empty (`len > 0`) and its last character (`sb.charAt(len - 1)`) is the same as the current character `c`, then we have found an adjacent duplicate. Remove the last character from the `StringBuilder` using `sb.deleteCharAt(len - 1)`.
- Otherwise, append the current character `c` to the `StringBuilder`.
- After the loop finishes, convert the `StringBuilder` to a string and return it.

# Solutions
### Java

```java
class Solution {
public
  String removeDuplicates(String s) {
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray()) {
      if (sb.length() > 0 && sb.charAt(sb.length() - 1) == c) {
        sb.deleteCharAt(sb.length() - 1);
      } else {
        sb.append(c);
      }
    }
    return sb.toString();
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @return {string} */ var removeDuplicates = function ( s ) { const stk = []; for ( const c of s ) { if ( stk . length && stk [ stk . length - 1 ] == c ) { stk . pop (); } else { stk . push ( c ); } } return stk . join ( '' ); };
```

### CPP

```cpp
class Solution { public: string removeDuplicates ( string s ) { string stk ; for ( char c : s ) { if ( ! stk . empty () && stk [ stk . size () - 1 ] == c ) { stk . pop_back (); } else { stk += c ; } } return stk ; } };
```

### Python

```python
class Solution:
    def removeDuplicates(self, s: str) -> str: stk = [] for c in s: if stk and stk[- 1] == c: stk . pop() else: stk . append(c) return '' . join(stk)

```