1. Understanding the Problem

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

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

For example, "ab#c" turns into "ac" because the '#' erases the character 'b' right before it. Similarly, "ab##" becomes an empty string because the two consecutive backspaces remove both 'b' and 'a'.

The Core Challenge:

While dynamic character deletion can be simulated easily with auxiliary data structures, doing so requires extra memory. The true test in an interview is handling backspace cancellations on the fly.

2. The Naive Approach: Stack Simulation

The most intuitive way to handle the problem is to build the final string for both s and t independently using a Stack or dynamic array, then compare the two processed strings character by character.

Trade-off Analysis

While this strategy is easy to reason about, it incurs additional overhead:

• Time Complexity: O(N + M) — Linear scan through both strings of lengths N and M.
• Space Complexity: O(N + M) — Creating dynamic stacks allocates extra memory proportional to string length.

3. The Optimal Approach: Reverse Two-Pointer Traversal (O(N) Time, O(1) Space)

To pass a senior-level technical interview, we want to achieve a clean single-pass O(N + M) time complexity with strictly O(1) auxiliary space.

Instead of reading left to right (where a backspace deletes a character we already passed), we iterate right to left from the end of both strings. When moving backward:

• A backspace character '#' tells us to skip the next valid character we encounter to its left.
• We maintain a count of active backspaces for each string to know how many non-'#' characters to ignore.
• Once both pointers land on their next surviving character, we compare them. If they match, we continue backward; if not, we return false.

This single observation completely unifies the logic, seamlessly handling multiple backspaces and empty states without any string allocations!

4. The Logic Step-by-Step

1. Initialize pointers i = len(s) - 1 and j = len(t) - 1, along with skip_s = 0 and skip_t = 0.
2. Outer Loop: While i >= 0 or j >= 0:
   • Find Valid Char in s: Loop backward using i. Increment skip_s on '#', or decrement skip_s and move left if skip_s > 0. Stop when reaching a valid character.
   • Find Valid Char in t: Loop backward using j. Increment skip_t on '#', or decrement skip_t and move left if skip_t > 0. Stop when reaching a valid character.
   • Compare Characters:
     • If both i and j are valid indices, check if s[i] == t[j]. If not, return false.
     • If one string has a remaining valid character while the other string is exhausted, return false.
3. Return true if pointers finish traversing both strings without mismatches.

5. Complexity Analysis

• Time Complexity: O(N + M) — We traverse each character of string s (length N) and string t (length M) at most once.
• Space Complexity: O(1) — Memory usage remains strictly constant as we only store a few pointer and count variables.

6. Code Implementations

Expand the sections below to see the optimal O(1) space "Reverse Two-Pointer Traversal" implementations across different languages.

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        i, j = len(s) - 1, len(t) - 1
        skip_s, skip_t = 0, 0

        while i >= 0 or j >= 0:
            # Find index of next valid character in s
            while i >= 0:
                if s[i] == '#':
                    skip_s += 1
                    i -= 1
                elif skip_s > 0:
                    skip_s -= 1
                    i -= 1
                else:
                    break

            # Find index of next valid character in t
            while j >= 0:
                if t[j] == '#':
                    skip_t += 1
                    j -= 1
                elif skip_t > 0:
                    skip_t -= 1
                    j -= 1
                else:
                    break

            # Compare valid characters
            if i >= 0 and j >= 0:
                if s[i] != t[j]:
                    return False
            # If one string ran out of characters while the other didn't
            elif (i >= 0) != (j >= 0):
                return False

            i -= 1
            j -= 1

        return True

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

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

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

            // Compare valid characters
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            } else if ((i >= 0) != (j >= 0)) {
                return false;
            }

            i--;
            j--;
        }

        return true;
    }
}

#include <string>

class Solution {
public:
    bool backspaceCompare(std::string s, std::string t) {
        int i = s.length() - 1;
        int j = t.length() - 1;
        int skipS = 0;
        int skipT = 0;

        while (i >= 0 || j >= 0) {
            // Find index of next valid character in s
            while (i >= 0) {
                if (s[i] == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }

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

            // Compare valid characters
            if (i >= 0 && j >= 0) {
                if (s[i] != t[j]) {
                    return false;
                }
            } else if ((i >= 0) != (j >= 0)) {
                return false;
            }

            i--;
            j--;
        }

        return true;
    }
};

7. Conclusion: You Are Ready

Congratulations, you have just mastered the "Backspace String Compare" pattern! The key takeaway from this problem is discovering the unifying directional insight: when backspace actions invalidate past elements, reading backward converts unknown future operations into manageable skip counts. By leveraging two reverse pointers, you converted what could have required auxiliary data structures into an optimal O(1) space solution. Keep this reverse two-pointer technique in your mental toolkit, as it is a crucial pattern for stream processing and string editing interview questions!