# Backspace String Compare
**Difficulty:** EASY
[External](https://leetcode.com/problems/backspace-string-compare)
Canonical: https://scaleengineer.com/dsa/problems/backspace-string-compare
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String, Stack
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [Chewy](https://scaleengineer.com/companies/chewy), [IBM](https://scaleengineer.com/companies/ibm), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Wayfair](https://scaleengineer.com/companies/wayfair), [Microstrategy](https://scaleengineer.com/companies/microstrategy), [Booking.com](https://scaleengineer.com/companies/booking.com), [Amdocs](https://scaleengineer.com/companies/amdocs), [Grammarly](https://scaleengineer.com/companies/grammarly), [Roku](https://scaleengineer.com/companies/roku)
---
## Problem
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 s and t become "ac".

**Example 2:**

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

**Example 3:**

**Input:** s = "a#c", t = "b"
**Output:** false
**Explanation:** s becomes "c" while t becomes "b".

**Constraints:**

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

**Follow up:** Can you solve it in `O(n)` time and `O(1)` space?

# Approaches
## Build Final Strings
This approach simulates the process of typing the characters of each string into a text editor. We can build the final resulting strings for both `s` and `t` after processing all the backspace characters. Finally, we compare the two built strings to see if they are identical.
**Time:** O(N + M), where N and M are the lengths of strings `s` and `t` respectively. We iterate through each string once to build the final strings, and then compare them. · **Space:** O(N + M). In the worst case (no backspaces), the `StringBuilder`s will store all characters of the original strings, where N and M are the lengths of s and t.
**Pros:** Conceptually simple and easy to implement.; The logic directly follows the problem description.
**Cons:** Requires extra space proportional to the input string lengths, which does not meet the follow-up constraint of O(1) space.
### Explanation
We can write a helper function that takes a string and returns its final version after applying backspaces. This function iterates through the input string and uses a `StringBuilder` (or a stack) to construct the result.
- When a non-backspace character is encountered, it's appended to the `StringBuilder`.
- When a backspace character ('#') is found, if the `StringBuilder` is not empty, the last character is deleted.
- After processing both `s` and `t` with this helper function, we get two final strings. The problem then reduces to a simple string comparison.
```java
class Solution {
    public boolean backspaceCompare(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();
    }
}
```
### Algorithm
- Create a helper function `build(String str)`.
- Inside `build`, initialize an empty `StringBuilder`.
- Iterate through each character of the input string `str`.
- If the character is not '#', append it to the `StringBuilder`.
- If the character is '#' and the `StringBuilder` is not empty, remove its last character.
- After the loop, return the string representation of the `StringBuilder`.
- In the main function, call `build(s)` and `build(t)`.
- Compare the two resulting strings for equality and return the result.

## Two Pointers from the End
To solve the problem in O(1) space, we can avoid creating new strings. Instead, we can compare the characters of `s` and `t` one by one, from right to left. Iterating from the end is beneficial because a backspace character '#' tells us to skip the next valid character to its left. This approach allows us to find the next character that would appear in the final string without actually building it.
**Time:** O(N + M), where N and M are the lengths of `s` and `t`. Although there are nested loops, each character of `s` and `t` is visited at most twice, so the complexity is linear. · **Space:** O(1). We only use a constant amount of extra space for pointers and counters, regardless of the input size.
**Pros:** Highly efficient in terms of space, meeting the O(1) space complexity follow-up.; Time complexity is also optimal at O(N + M).
**Cons:** The logic is more complex than the build-string approach, with nested loops and multiple conditions to manage.; Can be slightly harder to debug if implemented incorrectly.
### Explanation
We use two pointers, `i` and `j`, initialized to the end of strings `s` and `t` respectively. We iterate backwards as long as there are characters to process in either string.
In each step of the main loop, we find the next valid character in `s` and `t`. A valid character is one that is not a backspace and is not skipped by a backspace.
- To find the next valid character in `s` (similarly for `t`), we use an inner loop. We also maintain a `skip` counter. If we see a '#', we increment `skip` and move the pointer left. If we see a non-'#' character while `skip > 0`, we decrement `skip` and move the pointer left (as this character is 'deleted'). We stop when we find a non-'#' character with `skip == 0`, or when the pointer goes out of bounds.
- After finding the next valid characters from both strings (or determining that one string is exhausted), we compare them.
- If the characters are different, the strings are not equivalent, and we return `false`.
- If one string has a valid character while the other is exhausted, they are not equivalent, so we return `false`.
- If both are exhausted simultaneously or the characters match, we continue by moving both pointers to the left.
- If the entire loop completes, it means the strings are equivalent, and we return `true`.
```java
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 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;
                }
            }

            // If two actual characters are different
            if (i >= 0 && j >= 0 && s.charAt(i) != t.charAt(j)) {
                return false;
            }
            
            // If one string is empty while the other is not
            if ((i >= 0) != (j >= 0)) {
                return false;
            }

            i--;
            j--;
        }

        return true;
    }
}
```
### Algorithm
- Initialize two pointers, `i` to `s.length() - 1` and `j` to `t.length() - 1`.
- Initialize two skip counters, `skipS` and `skipT`, to 0.
- Loop while `i >= 0` or `j >= 0`.
- Inside the loop, find the next valid character for `s`: use a nested `while` loop that moves `i` left. If `s.charAt(i)` is '#', increment `skipS`. If `s.charAt(i)` is a letter and `skipS > 0`, decrement `skipS`. Break when a valid character is found (letter with `skipS == 0`).
- Similarly, find the next valid character for `t` using pointer `j` and counter `skipT`.
- After finding the valid characters (or reaching the beginning of a string), compare their states:
- If both `i` and `j` are valid indices and `s.charAt(i)` is not equal to `t.charAt(j)`, return `false`.
- If one pointer is valid (`>= 0`) and the other is not, it means the effective lengths are different. Return `false`.
- Decrement both `i` and `j` to proceed to the next characters.
- If the main loop completes, it means the strings are equivalent. Return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean backspaceCompare(String s, String t) {
    int i = s.length() - 1, j = t.length() - 1;
    int skip1 = 0, skip2 = 0;
    for (; i >= 0 || j >= 0; --i, --j) {
      while (i >= 0) {
        if (s.charAt(i) == '#') {
          ++skip1;
          --i;
        } else if (skip1 > 0) {
          --skip1;
          --i;
        } else {
          break;
        }
      }
      while (j >= 0) {
        if (t.charAt(j) == '#') {
          ++skip2;
          --j;
        } else if (skip2 > 0) {
          --skip2;
          --j;
        } else {
          break;
        }
      }
      if (i >= 0 && j >= 0) {
        if (s.charAt(i) != t.charAt(j)) {
          return false;
        }
      } else if (i >= 0 || j >= 0) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool backspaceCompare(string s, string t) {
    int i = s.size() - 1, j = t.size() - 1;
    int skip1 = 0, skip2 = 0;
    for (; i >= 0 || j >= 0; --i, --j) {
      while (i >= 0) {
        if (s[i] == '#') {
          ++skip1;
          --i;
        } else if (skip1) {
          --skip1;
          --i;
        } else
          break;
      }
      while (j >= 0) {
        if (t[j] == '#') {
          ++skip2;
          --j;
        } else if (skip2) {
          --skip2;
          --j;
        } else
          break;
      }
      if (i >= 0 && j >= 0) {
        if (s[i] != t[j])
          return false;
      } else if (i >= 0 || j >= 0)
        return false;
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool: i, j, skip1, skip2 = len(s) - 1, len(t) - 1, 0, 0 while i >= 0 or j >= 0: while i >= 0: if s[i] == '#': skip1 += 1 i -= 1 elif skip1: skip1 -= 1 i -= 1 else: break while j >= 0: if t[j] == '#': skip2 += 1 j -= 1 elif skip2: skip2 -= 1 j -= 1 else: break if i >= 0 and j >= 0: if s[i] != t[j]: return False elif i >= 0 or j >= 0: return False i, j = i - 1, j - 1 return True

```