easy Remove All Adjacent Duplicates In String

Problem Statement

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.

Examples

- Input: s = "abccba"
- Output: ""
- Explanation: First, we remove "cc" to get "abba". Then, we remove "bb" to get "aa". Finally, we remove "aa" to get an empty string.
- Input: s = "foobar"
- Output: "fbar"
- Explanation: We remove "oo" to get "fbar".
- Input: s = "fooobar"
- Output: "fobar"
- Explanation: We remove the pair "oo" to get "fobar".
- Input: s = "abcd"
- Output: "abcd"
- Explanation: No adjacent duplicates so no changes.

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Remove All Adjacent Duplicates In String easy

0. Why / judgment (K3)

Family: Stack · adjacent pair elimination

Repeatedly delete adjacent equals is exactly stack collapse: push char; if top matches, pop (delete pair). Cascades handled automatically ("abba" → empty). Linear one pass.

1. Pattern + recognition + when-NOT (K12)

Pattern / template: stack=[]; for c in s: if stack and stack[-1]==c: pop else push. return join(stack). Recognition: cancel adjacent pairs / string reduction.

When-NOT: Not k-adjacent duplicates (need count stack — Remove Duplicates II). Not anagram. Not two pointers only without stack if cascading from left carefully — stack is cleanest. Regex replace loop can be quadratic.

2. Complexity derivation (K11)

Each char pushed/popped at most once → Θ(n) time.
Space Θ(n) worst (no duplicates).

3. Edge hand-run (K13)

"abccba": push a,b,c; pop c; pop b; pop a → "".
"foobar": … oo pop → "fbar".
"fooobar": oo pop → "fobar".
"abcd" unchanged. Empty → empty.

4. Interviewer follow-ups & drills

Q1. Why not two-pointer in-place only?
Model answer: Works with write index similar to stack; same idea.

Q2. k=3 variant?
Model answer: Store (char,count); pop when count hits k.

Q3. Mis-tag sliding window?
Model answer: Not subarray metric; stack reduction.

✅ Solution Remove All Adjacent Duplicates In String

Problem Statement

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.

Examples

- Input: s = "abccba"
- Output: ""
- Explanation: First, we remove "cc" to get "abba". Then, we remove "bb" to get "aa". Finally, we remove "aa" to get an empty string.
- Input: s = "foobar"
- Output: "fbar"
- Explanation: We remove "oo" to get "fbar".
- Input: s = "fooobar"
- Output: "fobar"
- Explanation: We remove the pair "oo" to get "fobar".
- Input: s = "abcd"
- Output: "abcd"
- Explanation: No adjacent duplicates so no changes.

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.

Solution

This problem can be solved efficiently using a stack, which can mimic the process of eliminating adjacent duplicates.

Algorithm Walkthrough

Initialize an empty stack.
Loop through the characters in the given string s.
For each character:
- If the stack is not empty and the current character is the same as the top character on the stack, pop the character from the stack.
- Otherwise, push the current character onto the stack.
Finally, build the result string from the characters remaining on the stack.

Code

Here is the code for this algorithm:

java

import java.util.Stack;

public class Solution {

  public String removeDuplicates(String s) {
    // Initialize stack
    Stack<Character> stack = new Stack<>();

    // Process each character in s
    for (char c : s.toCharArray()) {
      // If the stack is not empty and the current character is the same as the top of the stack, pop the character from the stack
      if (!stack.isEmpty() && c == stack.peek()) {
        stack.pop();
      } else { // Push the current character onto the stack
        stack.push(c);
      }
    }

    // Join the stack to a string
    StringBuilder result = new StringBuilder();
    for (Character c : stack) {
      result.append(c);
    }
    return result.toString();
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.removeDuplicates("abccba")); // Output: ""
    System.out.println(solution.removeDuplicates("foobar")); // Output: "fbar"
    System.out.println(solution.removeDuplicates("abcd")); // Output: "abcd"
  }
}

Time and Space Complexity

The time complexity of this algorithm is , where N is the length of s, because we perform one operation per character in s. The space complexity is also , as in the worst case, every character in s is pushed onto the stack.

🎯 STRICT STANDOUT — Solution Remove All Adjacent Duplicates In String

0. Why / judgment (K3)

Family: Stack reduction

Invariant: stack always holds the fully reduced prefix processed so far. New char either extends or cancels top — no need to rescan earlier.

1. Pattern + recognition + when-NOT (K12)

Pattern / template: Monotonic-ish stack of unmatched chars (not value-monotonic — equality cancel).

When-NOT: Recursive remove is O(n²) string rebuild risk.

2. Complexity derivation (K11)

T=Θ(n), S=Θ(n).

3. Edge hand-run (K13)

Hand-run "abbaca": a,b,b→pop b → a,a→pop a → c,a → "ca".
All same even length → empty; odd → one char.

4. Interviewer follow-ups & drills

Q1. Prove linear
Model answer: Amortized: ≤n pushes, ≤n pops.

Q2. In-place array?
Model answer: Use write pointer as stack top index.

Q3. Case sensitive?
Model answer: Yes; 'A'≠'a'.

🧩 Pattern · Stack

Recognize it: Matching / nesting, or “next greater / smaller” → LIFO, or a monotonic stack.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Remove All Adjacent Duplicates In String? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Remove All Adjacent Duplicates In String** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Remove All Adjacent Duplicates In String** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Remove All Adjacent Duplicates In String**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Remove All Adjacent Duplicates In String**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Isomorphic Strings Can Place Flowers →