Backspace String Compare

[!NOTE] This problem highlights the difference between building a result (Stack) and verifying a result (Two Pointers). While the Stack approach is more intuitive, scanning backwards allows for constant space optimization.

---

1. Problem Definition

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

• Input: s = "ab#c", t = "ad#c"
• Output: true
• Explanation: Both become "ac".

Example 2:

• Input: s = "ab##", t = "c#d#"
• Output: true
• Explanation: Both become "".

Constraints:

• 1 <= s.length, t.length <= 200
• s and t only contain lowercase letters and '#'.

---

2. Interactive Analysis

String S: ab#c

String T: ad#c

Click a strategy to see how strings are compared.

---

3. Intuition

Approach 1: The Stack Strategy (Building the String)

The most natural way to handle a backspace is “Last-In, First-Out”.

1. Iterate through the string.
2. If the character is not #, push it onto the stack.
3. If the character is #, pop the last character (if any).
4. Compare the resulting strings.
   • Why?: It mimics the actual behavior of a text editor perfectly.

Approach 2: The Two-Pointer Strategy (Space Optimized)

Can we compare them without building new strings? When we see a character, we only know if it survives after looking at the backspaces that follow it. This suggests scanning backwards.

1. Start from the end of both strings.
2. Maintain a skip count for each string.
3. If you see #, increment skip.
4. If you see a character and skip > 0, ignore it and decrement skip.
5. If you see a character and skip == 0, this is a “valid” character that must match the corresponding character in the other string.
   • Why?: This allows $O(1)$ space because we don’t store the processed strings.

---

4. Solutions

Java

Go

class Solution {
    /**
     * Approach 1: Two-Pointer (Space Optimized)
     * Time: O(N) | Space: O(1)
     */
    public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1, j = t.length() - 1;
        int sSkip = 0, tSkip = 0;

        while (i >= 0 || j >= 0) {
            // Find next valid char in S
            while (i >= 0) {
                if (s.charAt(i) == '#') { sSkip++; i--; }
                else if (sSkip > 0) { sSkip--; i--; }
                else break;
            }
            // Find next valid char in T
            while (j >= 0) {
                if (t.charAt(j) == '#') { tSkip++; j--; }
                else if (tSkip > 0) { tSkip--; j--; }
                else break;
            }

            // Compare valid characters
            if (i >= 0 && j >= 0 && s.charAt(i) != t.charAt(j)) return false;
            // If one string ends but the other doesn't
            if ((i >= 0) != (j >= 0)) return false;
            
            i--; j--;
        }
        return true;
    }

    /**
     * Approach 2: Stack (Intuitive)
     * Time: O(N) | Space: O(N)
     */
    public boolean backspaceCompareStack(String s, String t) {
        return build(s).equals(build(t));
    }

    private String build(String str) {
        StringBuilder sb = new StringBuilder();
        for (char c : str.toCharArray()) {
            if (c != '#') {
                sb.append(c);
            } else if (sb.length() > 0) {
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        return sb.toString();
    }
}

/**
 * Approach 1: Two-Pointer (Space Optimized)
 * Time: O(N) | Space: O(1)
 */
func backspaceCompare(s string, t string) bool {
    i, j := len(s)-1, len(t)-1
    skipS, skipT := 0, 0

    for i >= 0 || j >= 0 {
        // Find next valid character in s
        for i >= 0 {
            if s[i] == '#' {
                skipS++
                i--
            } else if skipS > 0 {
                skipS--
                i--
            } else {
                break
            }
        }
        // Find next valid character in t
        for j >= 0 {
            if t[j] == '#' {
                skipT++
                j--
            } else if skipT > 0 {
                skipT--
                j--
            } else {
                break
            }
        }

        // Check if characters match
        if i >= 0 && j >= 0 && s[i] != t[j] {
            return false
        }
        // Check if one finished before the other
        if (i >= 0) != (j >= 0) {
            return false
        }
        i--
        j--
    }
    return true
}

/**
 * Approach 2: Stack (Simulated with Slice)
 * Time: O(N) | Space: O(N)
 */
func backspaceCompareStack(s string, t string) bool {
    return build(s) == build(t)
}

func build(str string) string {
    stack := []rune{}
    for _, c := range str {
        if c != '#' {
            stack = append(stack, c)
        } else if len(stack) > 0 {
            stack = stack[:len(stack)-1]
        }
    }
    return string(stack)
}

---

5. Complexity Analysis

Strategy	Time Complexity	Space Complexity	Hardware Connection
Stack	$O(N + M)$	$O(N + M)$	Easy to implement; uses heap memory for StringBuilder/Slice.
Two Pointers	$O(N + M)$	$O(1)$	Optimal; avoids extra allocations and GC pressure.