Backspace String Compare: 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.

Try this Problem on your own or check similar problems:

1. Crawler Log Folder
2. Longest Mountain in Array
3. Removing Stars From a String

Solution:

public boolean backspaceCompare(String s, String t) {
    int i = s.length() - 1, j = t.length() - 1;
    int skipCharS = 0, skipCharsT = 0;

    while (i >= 0 || j >= 0) {
        while (i >= 0) {
            if (s.charAt(i) == '#') {
                ++skipCharS;
                --i;
            }
            else if (skipCharS > 0) {
                --skipCharS;
                --i;
            }
            else break;
        }
        while (j >= 0) {
                if (t.charAt(j) == '#') {
                ++skipCharsT;
                --j;
            }
            else if (skipCharsT > 0) {
                --skipCharsT;
                --j;
            }
            else break;
        }

        if (i >= 0 && j >= 0 && s.charAt(i) != t.charAt(j))
            return false;

        if ((i >= 0) != (j >= 0))
            return false;

        --i;
        --j;
    }

    return true;
}

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

Explanation:

If we assume linear space complexity the problem would become trivial (using stack or string builder in java to clean up the string and then compare them), but the follow up question will probably be to do it with constant space complexity. We utilize the two pointers approach while also keeping the number of characters for each string we have to skip since they would get deleted because of the existing backspace later in the string. With that in mind it makes sense to iterate over strings from end to start while there are still elements to visit for each string (that’s why at the end of outer loop we check (i >= 0) != (j >= 0) if one of the strings doesn’t have any characters left while the other has, the strings aren’t equal). Just before that we check for the current char equality for both (non-empty) strings. The most important part of the solution is the first two inner loops respectively iteration over s and t. The point of each of those two loops is to find the next character to compare. How do we find that character? Well, we have two cases either we encounter '#' we move i or j pointer to the left and increase the number of times we have to skip the next characters. Once we find a non # character we check how many characters will get skipped/deleted based on the previous # (e.g. skipCharS > 0 for s string). If we do, we just skip the current character and decrement the number of times we have to skip (number of so far visited '#'). If there is nothing to skip, we find ourselves next character to compare and we do this for both of the strings and at the end we compare those two new candidates. Time complexity is O(n) where n is the length of smaller string.