Two PointersMediumO(n + m) time · O(1) space

Comparing Strings containing Backspaces

Mahabharata — Ganesha Transcribing the Mahabharata — Erasing Mistakes from Both Ends

लेखनीयं यदा नश्यति मध्ये विलोपनेन। अन्तात् पठन् तुलनीयं सत्यमेव विजयते॥

*When writing is destroyed midway by erasure, read from the end and compare — only truth prevails.*

The Story

The night was absolute. No lamps burned in that sacred grove on the slopes of Meru where Vyasa had summoned Ganesha to be his scribe. The Mahabharata was being born.

"I have one condition," Ganesha had said, his trunk curled in mild amusement. "You must dictate without pause. If you stop, I stop writing and leave."

"And I have one condition," Vyasa had replied, the sage's eyes glinting. "You must not write a single syllable whose meaning you do not fully comprehend."

Thus began the greatest composition in human history. Vyasa would sometimes speak in riddles dense enough to make even Ganesha pause and think, buying the sage precious moments to compose the next verse. And when Ganesha's feather-pen scratched out an error on the palm-leaf scroll, he would drag the back of his tusk across it — the ancient backspace.

Days into the dictation, a dispute arose.

Vyasa had composed two nearly identical invocations — the opening prayers to each of the eighteen parvas. Both were meant to be identical, yet Ganesha suspected errors had crept into one or both through the erasures.

"Let me compare them," Ganesha said, unrolling both scrolls side by side.

The young apprentice scribe Sauti, who had been watching, suggested eagerly: "Lord Ganesha, I can build both texts fresh — scan each scroll character by character, apply all the erasures, then compare the final strings!"

"That would require extra scroll-space proportional to the length of each text," Ganesha replied, his elephant eyes patient. "We are scribing the longest poem in history. We cannot keep full copies of processed strings in memory."

"Then how?"

Ganesha held up both scrolls side by side, one in each hand, and pointed his reading tusk at the END of each — not the beginning.

"I read backwards," he said simply.

Sauti frowned. "But the erasures are scattered throughout—"

"And that is exactly why backward reading works." Ganesha pointed at an erasure mark (represented as #) near the end of Scroll A: `...ram#a...`

"When I encounter an erasure from the right, I know it cancels the character just before it. So I count erasures as I step left. Each # I encounter means the next real character I hit must be skipped. When my erasure-counter reaches zero, the character I land on is the next actual character to compare."

He demonstrated:

**Scroll A:** `ab#c` **Scroll B:** `ad#c`

"Starting from the right on Scroll A: I see `c`. Zero erasures. This `c` is real." "On Scroll B: I see `c`. Zero erasures. Real." "They match. Move both pointers left."

"On A: I see `#`. Erasure count = 1. Move left." "On A: I see `b`. Erasure count > 0, so `b` is erased. Count becomes 0. Move left." "On A: I see `a`. Count = 0, so `a` is real."

"On B: I see `#`. Erasure count = 1. Move left." "On B: I see `d`. Erased. Count becomes 0. Move left." "On B: I see `a`. Count = 0, so `a` is real."

"Both give `a`. They match. Pointers exhausted. The scrolls are identical in meaning!"

Sauti was astonished. "You never built the processed strings at all! You compared the scrolls directly in place, using only two pointer positions and two erasure counters!"

"Four integers total," Ganesha confirmed. "Two positions, two counters. O(1) space. And each character is visited at most once going rightward, so O(n+m) time where n and m are the scroll lengths."

"But what about multiple consecutive erasures?" Sauti pressed. "What if someone typed `abc###`?"

"The erasure counter handles it. Each # increments the counter by 1. Each real character, if the counter is positive, is erased and the counter decrements. Only when the counter is zero do we have a real character to compare. Three erasures in a row means the next three real characters are all cancelled."

Vyasa, who had been listening from the shadows, spoke: "And what if one scroll is exhausted but the other still has real characters?"

"Then they differ," Ganesha said. "Inequality is revealed not just by mismatched characters, but by unequal lengths of effective text."

The two scrolls were confirmed identical. The parvas began with the same prayer. And the Mahabharata rolled on.

"Remember this," Ganesha told Sauti, who would one day narrate this epic to Saunaka's assembly. "When comparing strings with deletions, do not process them into new strings. Read from the end. Let the deletion marks guide you backward to the truth."

This is the Two Pointer technique for comparing strings with backspaces.

Sauti's First Instinct

Build both final strings first by processing each character and handling backspaces with a stack. Then compare the two resulting strings. Uses O(n+m) extra space.

java

public boolean backspaceCompareBruteForce(String s, String t) {
    // Build final string for s
    StringBuilder sbS = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (c == '#') {
            // Backspace: remove last character if any
            if (sbS.length() > 0) sbS.setLength(sbS.length() - 1);
        } else {
            sbS.append(c);
        }
    }
    
    // Build final string for t
    StringBuilder sbT = new StringBuilder();
    for (char c : t.toCharArray()) {
        if (c == '#') {
            if (sbT.length() > 0) sbT.setLength(sbT.length() - 1);
        } else {
            sbT.append(c);
        }
    }
    
    // Compare the two processed strings
    return sbS.toString().equals(sbT.toString());
}

Ganesha's Wisdom

Ganesha's insight: read both strings from the END. Maintain an erasure counter per string. Moving left: - If we see `#`: increment erasure counter - If we see a real char but counter > 0: this char is erased, decrement counter, keep moving - If we see a real char and counter == 0: this is the next effective character to compare Compare effective characters from both strings simultaneously. Any mismatch or length difference means not equal.

java

public boolean backspaceCompare(String s, String t) {
    int i = s.length() - 1, j = t.length() - 1;
    
    while (i >= 0 || j >= 0) {
        // Find next real character in s
        i = nextRealChar(s, i);
        // Find next real character in t
        j = nextRealChar(t, j);
        
        // Both exhausted — equal
        if (i < 0 && j < 0) return true;
        // One exhausted but not the other — unequal length
        if (i < 0 || j < 0) return false;
        // Characters differ
        if (s.charAt(i) != t.charAt(j)) return false;
        
        // Both matched, move left
        i--;
        j--;
    }
    return true;
}

// Returns index of next real (undeleted) character scanning left from pos
private int nextRealChar(String str, int pos) {
    int backspaces = 0;
    while (pos >= 0) {
        if (str.charAt(pos) == '#') {
            backspaces++;  // This erases the char to its left
            pos--;
        } else if (backspaces > 0) {
            backspaces--;  // This char is erased
            pos--;
        } else {
            break;  // This char is real
        }
    }
    return pos;
}

// Test with Ganesha's scrolls
public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.backspaceCompare("ab#c", "ad#c"));  // true (both = "ac")
    System.out.println(sol.backspaceCompare("ab##", "c#d#"));  // true (both = "")
    System.out.println(sol.backspaceCompare("a#c", "b"));       // false ("c" vs "b")
}

Step-by-Step Walkthrough

s = "y#fo##f",  t = "y#f#o##f"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Find real char in s from index 6:
  s[6]='f' → counter=0 → real 'f' at i=6
Find real char in t from index 7:
  t[7]='f' → counter=0 → real 'f' at j=7
Compare: 'f' == 'f' ✓  → i=5, j=6

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Find real char in s from index 5:
  s[5]='#' → counter=1 → i=4
  s[4]='#' → counter=2 → i=3
  s[3]='o' → counter=2>0, erased → i=2
  s[2]='f' → counter=1>0, erased → i=1
  s[1]='#' → counter=2 → i=0
  s[0]='y' → counter=2>0, erased → i=-1
Real char in s: NONE (i=-1)

Find real char in t from index 6:
  t[6]='#' → counter=1 → j=5
  t[5]='#' → counter=2 → j=4
  t[4]='o' → counter=2>0, erased → j=3
  t[3]='#' → counter=3 → j=2
  t[2]='f' → counter=3>0, erased → j=1
  t[1]='#' → counter=4 → j=0
  t[0]='y' → counter=4>0, erased → j=-1
Real char in t: NONE (j=-1)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Both i<0 and j<0 → return true ✅

✅ Both strings process to "f" — they are equal

Deep Insight

**Why read from the end?**

Backspace affects the character BEFORE it. If you read forward, seeing '#' tells you a character you already passed is deleted — you'd need to go back and undo. Reading backward makes '#' mean "skip the next real character I encounter going left", which is naturally handled by a counter without backtracking.

**The counter invariant:** At any point, `backspaces` = the number of real characters still to be erased as we scan left. When it hits 0, the next real character is our comparison candidate.

**Edge cases:** - `"a##"`: counter reaches 2, but there's only 1 real char ('a') before '#'. The 'a' is erased, counter becomes 1. No more chars. Result: empty string. - `"###"`: All deletions, no real chars. Result: empty string. - Leading backspaces: `"#a"` — the '#' tries to erase nothing (already at left boundary), 'a' is real. - Different lengths of processed strings: caught naturally when one pointer hits -1 before the other.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n + m)	O(n + m)	Two full StringBuilders holding processed results
Optimal	O(n + m)	O(1)	Only 4 integers: two pointers + two counters

Pattern Recognition

✅ Two strings that need character-by-character comparison
✅ Deletions/modifications affect the string in-place
✅ O(1) space requirement
✅ Characters are visited once, no re-processing needed

**LeetCode Trigger Phrases:**
→ "backspace character" + "compare two strings"
→ "'#' means delete the previous character"
→ "determine if the two strings are equal"

Bhagavad Gita 5.16

ज्ञानेन तु तदज्ञानं येषां नाशितमात्मनः। तेषामादित्यवज्ज्ञानं प्रकाशयति तत् परम्॥

But for those whose ignorance of the self is destroyed by knowledge, that knowledge illuminates the Supreme like the sun.

Connection: The backspace in writing is like ignorance obscuring truth — it erases what came before. But reading from the end with wisdom (the pointer + counter technique), we cut through all the erasures and see only what truly remains. Just as knowledge destroys accumulated ignorance to reveal the pure self, the algorithm strips away all '#' marks to reveal the final, true form of each string.