Backspace String Compare

Problem Link

844. Backspace String Compare – LeetCode

Problem Statement

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 string, nothing happens.

Examples

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 "".

Example 3:

Input: s = "a#c", t = "b"
Output: false

Constraints

• 1 <= s.length, t.length <= 200

• s and t only contain lowercase letters and '#' characters

Intuition

We need to simulate the behavior of a text editor that processes '#' as a backspace.

For both strings:

• Traverse character by character.

• Use a stack to emulate text editor behavior:

  • Push characters normally.

  • Pop when encountering '#'.

After processing both strings, compare the final results.

Approach: Stack-Based Simulation

1. Write a helper method removeBackspace(String str):

   • Initialize a Stack<Character>.

   • For each character:

     • If it's '#' and stack is not empty → pop.

     • If it's a letter → push to stack.

   • After processing, reconstruct the final string from the stack.

2. Process both strings and compare results.

Java Code

class Solution {
    public boolean backspaceCompare(String s, String t) {
        s = removeBackspace(s);
        t = removeBackspace(t); 
        return s.equals(t);
    }

    public String removeBackspace(String str) {
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (ch == '#' && !stack.isEmpty()) {
                stack.pop();
            } else if (ch != '#') {
                stack.push(ch);
            }
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        return sb.reverse().toString(); // reverse since we popped in reverse order
    }
}

Time and Space Complexity

Dry Run

Input:

s = "ab#c", t = "ad#c"

Steps:

• s → 'a' → 'b' → '#' → pop 'b' → 'c' → result: "ac"

• t → 'a' → 'd' → '#' → pop 'd' → 'c' → result: "ac"

"ac".equals("ac") → true

Follow-Up: O(1) Space Using Two Pointers

You can use two pointers from the end of both strings, skipping characters using backspace counts:

// Optimal space version: available on request

This achieves O(1) extra space and is optimal.

Conclusion

This problem demonstrates how stack-based simulation is useful for text editor logic and undo operations. It also introduces a follow-up on reducing space using two-pointer traversal.