Problem Statement

You are given two strings s and t. Each string may contain the backspace character #, which means the previous character should be deleted.

Your task is to determine if the two strings are equal after applying all backspace operations.

Example 1:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: 
- s becomes "ac"
- t becomes "ac"
- They are equal

Example 2:

Input: s = “a##c”, t = “#a#c”
Output: true
Explanation:

• s becomes “c”
• t becomes “c”

Example 3:

Input: s = "a#c", t = "b"
Output: false
Explanation: 
- s becomes "c"
- t becomes "b"
- They are not equal

Constraints:

• 1 <= s.length, t.length <= 200
• s and t consist of lowercase letters and '#'.

Approach 1: Using a Stack

The idea is simple:

1. Use a stack to process each string.
2. Iterate through the string:
   • If the character is not #, push it onto the stack.
   • If the character is # and the stack is not empty, pop the top element.
3. Compare the resulting stacks of both strings.

Java Implementation

import java.util.Stack;

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

    private String buildString(String str) {
        Stack<Character> stack = new Stack<>();
        for (char ch : str.toCharArray()) {
            if (ch != '#') {
                stack.push(ch);
            } else if (!stack.isEmpty()) {
                stack.pop();
            }
        }
        // Convert stack to string
        StringBuilder sb = new StringBuilder();
        for (char ch : stack) {
            sb.append(ch);
        }
        return sb.toString();
    }
}

Time Complexity: O(n + m), where n and m are the lengths of s and t.
Space Complexity: O(n + m), for the two stacks.

Approach 2: Two Pointers (Optimal, O(1) Space)

We can solve this without extra space by iterating the strings backwards:

1. Use two pointers i and j starting from the end of s and t.
2. Keep track of backspaces:
   • If the current character is #, increment a counter and move the pointer left.
   • If the counter is positive, skip the current character and decrement the counter.
3. Compare the characters after skipping backspaces.
4. If all characters match, return true.

public class Solution {
    public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1, j = t.length() - 1;

        while (i >= 0 || j >= 0) {
            int skipS = 0, skipT = 0;

            // Find next valid character in s
            while (i >= 0) {
                if (s.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }

            // Find next valid character in t
            while (j >= 0) {
                if (t.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }

            // Compare characters
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            } else if (i >= 0 || j >= 0) {
                // One string has characters left, other doesn't
                return false;
            }

            i--;
            j--;
        }

        return true;
    }
}

Time Complexity: O(n + m) – each character is visited at most twice.
Space Complexity: O(1) – no extra data structures used.