StackEasyO(n) time · O(n) space

Remove Adjacent Duplicates

Ramayana — Hanuman's Message Relay — Eliminating Repeated Words in the Sacred Scroll

यत्र पुनः पुनः एकं शब्दं श्रूयते। तत् द्वयं मिटयित्वा — शुद्धं सन्देशं प्रेषयेत्॥

*Where the same word is heard again and again — erase both and purify the message. Send forth the pure word.*

The Story

Given a string of lowercase letters, repeatedly remove all adjacent duplicates. Return the final string after all such removals.

For `s = "abbaca"`: `ab→baca` → remove `bb` → `aaca` → remove `aa` → `ca`. Answer: `"ca"`.

Hanuman was relaying a message from Rama. Any letter that repeated the one immediately before it (and its pair) had to be struck out — the message purified until no adjacent pair remained.

The stack approach is elegant: maintain a "current message" as a stack (or StringBuilder used as a stack).

For each character c: - If the stack is non-empty and the TOP equals c: **pop the top** (both cancel each other) - Otherwise: **push c**

Trace `"abbaca"`: - 'a': stack=[a] - 'b': top='a'≠'b' → push: [a,b] - 'b': top='b'=='b' → POP: [a] - 'a': top='a'=='a' → POP: [] - 'c': stack=[] → push: [c] - 'a': top='c'≠'a' → push: [c,a]

Stack = [c,a] → string = `"ca"` ✓

"The stack acts as memory of the 'last surviving character'," Hanuman noted. "Each new character checks against the most recent survivor. If they match, both are eliminated. If not, the new one joins the survivors."

The StringBuilder-as-stack approach avoids building an actual stack object — just use `sb.setLength(sb.length()-1)` to pop.

Hanuman's Repeated Scan

Repeatedly scan the string for adjacent duplicates, remove them, repeat until no changes. O(n²) — each scan removes at least one pair, and there can be n/2 pairs.

java

public String removeDuplicatesBruteForce(String s) {
    StringBuilder sb = new StringBuilder(s);
    boolean changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i < sb.length()-1; i++) {
            if (sb.charAt(i) == sb.charAt(i+1)) {
                sb.delete(i, i+2); changed = true; break;
            }
        }
    }
    return sb.toString();
}

Hanuman's Stack Wisdom

Use StringBuilder as a stack. For each character: if top equals current character, remove top (pop). Otherwise append (push). The result is the final non-duplicate string.

java

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.setLength(len - 1);  // Pop: remove the duplicate pair
        } else {
            sb.append(c);  // Push
        }
    }
    return sb.toString();
}

Step-by-Step Walkthrough

s="aabb"
'a'→[a]
'a'→pop: []
'b'→[b]
'b'→pop: []
Return "" ✅ (all eliminated)

Deep Insight

**Why one pass suffices?** The stack implicitly handles cascading removals. When 'b' is removed and the resulting top is the same as the next character, that next character will pop it too. No re-scanning needed.

**Example of cascading:** `"abccba"` → [a,b] → 'c' → [a,b,c] → 'c' pop → [a,b] → 'b' pop → [a] → 'a' pop → [] → return ""

**This is the foundation of st-7 (Remove K Adjacent Duplicates)** — where instead of removing pairs, we remove groups of k. Stack stores (char, count) pairs.

**StringBuilder efficiency:** Avoids creating a real Stack object — the string end IS the top of the stack.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n²)	O(n)	Repeated scans until no more pairs
Optimal	O(n)	O(n)	Single pass with stack — O(n) stack in worst case (no duplicates)

Pattern Recognition

✅ Remove adjacent duplicate characters
✅ Stack: push if top≠current, pop if top==current
✅ One pass, O(n)
✅ StringBuilder as stack for efficiency

**LeetCode Trigger Phrases:**
→ "remove all adjacent duplicates in string"
→ "eliminate pairs of identical adjacent characters"
→ Foundation for st-7 with k duplicates

Bhagavad Gita 2.52

यदा ते मोहकलिलं बुद्धिर्व्यतितरिष्यति। तदा गन्तासि निर्वेदं श्रोतव्यस्य श्रुतस्य च॥

When your intellect crosses the mire of delusion, then you will become indifferent to all that has been heard and all that is yet to be heard.

Connection: The stack removes redundancy — when the same character appears twice in succession, both are eliminated, leaving only what is truly distinct. Like the Gita's promise that wisdom crosses the 'mire of delusion' by discarding repeated false impressions, the algorithm purifies the string by eliminating every redundant echo, leaving only the genuine, non-repeating truth of the message.