Backspace String Compare

1. Problem Statement

Bob and Alice type two different strings. In their strings, the character # represents a backspace.

Whenever # appears, it removes the character immediately before it, if such a character exists.

Our task is to determine whether Bob's final text and Alice's final text are exactly the same.

If they are the same, print: 

YES

Otherwise, print: 

NO

2. Understanding Backspace

Suppose Bob types: 

abc#d

Let's process it step by step:

  • a → a
  • b → ab
  • c → abc
  • # → removes c, so we have ab
  • d → abd

    Therefore: 

    abc#d

    becomes: 

    abd

    Another example 

    ab##c

    Processing it:

    • a → a
    • b → ab
    • # → removes b, giving a
    • # → removes a, giving an empty string
    • c → c

      Final result: 

      c

      3. What Are We Comparing?

      Consider: 

      Bob:   ab#c
Alice: ac

      Bob's string: 

      ab#c

      The # removes b, so Bob ends with: 

      ac

      Alice already has: 

      ac

      Therefore, the answer is: 

      YES

      4. A Simple Approach

      One way to solve this problem is:

      1. Read Bob's string.
      2. Read Alice's string.
      3. Process each string and apply all backspaces.
      4. Compare the resulting strings.
      5. Print YES if they are equal; otherwise print NO.

        For beginners, this approach is very easy to understand.

        However, the original code uses a more efficient technique called the two-pointer approach.

        5. Two-Pointer Approach

        Instead of creating new strings after processing all the backspaces, we can examine both strings from right to left.

        Why right to left?

        Because a backspace affects the character immediately before it.

        For example: 

        abc##d

        When we start from the right side, we can easily keep track of how many characters should be skipped.

        We use: 

        int bobIndex = bob.size() - 1;
int aliceIndex = alice.size() - 1;

        These variables point to the current characters in the two strings.

        We also maintain two counters: 

        int bobBackspaces = 0;
int aliceBackspaces = 0;

        These counters tell us how many normal characters should be ignored because of backspaces.

        6. How the Backspace Counter Works

        Suppose we have: 

        abc##

        Starting from the right: 

        #

        This means one character must be deleted.

        So: 

        bobBackspaces++;

        Now we move left.

        We find another: 

        #

        So the counter becomes: 

        2

        Now we reach: 

        c

        Because there are two pending backspaces, c must be skipped.

        The counter becomes: 

        1

        Then we reach: 

        b

        It is also skipped.

        The counter becomes: 

        0

        The next character, a, is now a valid character.

        This allows us to find the actual characters that remain after applying all backspaces without physically modifying the string.

        7. Important Index Correction

        When using string::size(), remember that indexes start at 0.

        For example: 

        String:  a b c d
Index:   0 1 2 3

        The size is 4, but the last valid index is 3.

        Therefore, we should start from: 

        int index = str.size() - 1;

        not: 

        int index = str.size();

        The latter points one position past the end of the string and can cause an invalid memory access.

        8. Clean C++ Solution 

        #include <iostream>
#include <string>
using namespace std;

bool compareAfterBackspaces(const string& bob, const string& alice) {
    int bobIndex = static_cast<int>(bob.size()) - 1;
    int aliceIndex = static_cast<int>(alice.size()) - 1;

    int bobBackspaces = 0;
    int aliceBackspaces = 0;

    while (bobIndex >= 0 || aliceIndex >= 0) {

        // Find Bob's next valid character
        while (bobIndex >= 0) {
            if (bob[bobIndex] == '#') {
                bobBackspaces++;
                bobIndex--;
            }
            else if (bobBackspaces > 0) {
                bobBackspaces--;
                bobIndex--;
            }
            else {
                break;
            }
        }

        // Find Alice's next valid character
        while (aliceIndex >= 0) {
            if (alice[aliceIndex] == '#') {
                aliceBackspaces++;
                aliceIndex--;
            }
            else if (aliceBackspaces > 0) {
                aliceBackspaces--;
                aliceIndex--;
            }
            else {
                break;
            }
        }

        // Both strings have a valid character.
        if (bobIndex >= 0 && aliceIndex >= 0) {
            if (bob[bobIndex] != alice[aliceIndex]) {
                return false;
            }
        }
        // Only one string has a valid character.
        else if (bobIndex >= 0 || aliceIndex >= 0) {
            return false;
        }

        // Move to the next characters.
        bobIndex--;
        aliceIndex--;
    }

    return true;
}

int main() {
    string bob, alice;

    getline(cin, bob);
    getline(cin, alice);

    if (compareAfterBackspaces(bob, alice)) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }

    return 0;
}

        9. Detailed Example

        Suppose the input is: 

        ab#c
ac

        Bob 

        a b # c
0 1 2 3

        We start from the right: 

        c

        c is a normal character, so it is valid.

        Then we compare it with Alice's last valid character: 

        c

        They match.

        Next, Bob encounters: 

        #

        So: 

        bobBackspaces++;

        Now one character must be skipped.

        The character before # is: 

        b

        Therefore, b is ignored.

        The next valid Bob character is: 

        a

        Alice's next valid character is also: 

        a

        They match.

        Both strings have now been completely checked.

        Therefore: 

        YES

        10. Why Do We Move From Right to Left?

        Imagine: 

        hello#

        The # deletes the character immediately before it: 

        o

        When reading from the right, we encounter the # first. We immediately know that one previous character must be ignored.

        This makes it possible to process the string without creating another string.

        11. What Happens With Multiple Backspaces?

        Consider: 

        abc###

        Starting from the right: 

        #
#
#

        There are three pending backspaces.

        So the characters: 

        c
b
a

        are all removed.

        The final string is empty.

        This is correctly handled by the counter: 

        backspaces++;

        and later: 

        backspaces--;

        12. Important Edge Cases

        Case 1: Both strings are empty 

        Bob:   ""
Alice: ""

        Both result in empty strings.

        Output: 

        YES

        Case 2: Only backspaces 

        Bob:   ###
Alice: ##

        There are no characters to delete, so both become empty.

        Output: 

        YES

        Case 3: Different final characters 

        Bob:   abc
Alice: abd

        The final characters are different.

        Output: 

        NO

        Case 4: Different lengths but same result 

        Bob:   a#b
Alice: b

        Bob's a is removed by #, leaving: 

        b

        Both strings are therefore equal.

        Output: 

        YES

        13. Time Complexity

        Let:

        • n = length of Bob's string
        • m = length of Alice's string

          Each character is processed at most once.

          Therefore: 

          Time Complexity: O(n + m)

          We only use a few integer variables, so: 

          Space Complexity: O(1)

          This is better than creating separate processed strings when memory usage matters.

          14. Main Idea to Remember

          The most important concept is:

          A # creates a pending deletion for the character immediately to its left.

          When scanning from right to left:

          • # → increase the backspace counter.
          • Normal character + pending backspace → skip the character.
          • Normal character + no pending backspace → this is a character that remains.
          • Compare the remaining characters of Bob and Alice.

            If every remaining character matches, the two strings are equivalent after applying backspaces.

            15. Final Takeaway

            The problem is not really about comparing the original strings.

            It is about comparing the final strings after all # operations have been performed.

            The two-pointer technique lets us find those final characters efficiently without actually changing either input string.

            For beginners, first understand the backspace simulation using a stack or a new string. Once that idea is clear, the right-to-left two-pointer solution becomes much easier to understand.