Beats 100% | Easy Solution Using Two-Pointer with Reverse Iteration
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind this approach is to simulate typing the strings s and t into empty
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind this approach is to simulate typing the strings s and t into empty text editors while taking into account the backspace characters (\'#\'). We use two pointers, one for each string, to compare characters after removing backspaces.\n\n---\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialize two pointers, i and j, to the last indices of strings s and t, respectively. Also, initialize two variables, skipS and skipT, to keep track of the number of backspaces encountered for each string.\n\n2. Use a while loop to iterate as long as at least one of the strings has characters left to process (i >= 0 || j >= 0).\n\n3. For each string s and t, find the next character that is not a backspace (\'#\'):\n\n4. While i >= 0 and s[i] is a backspace (\'#\'), increment skipS and decrement i.\n- While j >= 0 and t[j] is a backspace (\'#\'), increment skipT and decrement j.\nCompare the current characters in s and t at indices i and j. If they are not equal and both i and j are valid indices, return false.\n\n5. If one of the strings has reached its end while the other hasn\'t, return false (e.g., if i >= 0 is not equal to j >= 0).\n\n6. Decrement i and j to move to the next characters in the strings.\n\n7. After the loop, if no mismatches are found, return true to indicate that the strings are equal.\n\n---\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of this approach is O(max(N, M)), where N is the length of string s and M is the length of string t. This is because in the worst case, we may have to process both strings completely.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity of this approach is O(1), as it uses a constant amount of extra space for variables, regardless of the input string lengths.\n\n\n---\n\n\n# Code\n```\nclass Solution {\npublic:\n    bool backspaceCompare(string s, string t) {\n        int i = s.length() - 1, j = t.length() - 1;\n        int skipS = 0, skipT = 0;\n\n        while (i >= 0 || j >= 0) {\n            while (i >= 0 && (s[i] == \'#\' || skipS > 0)) {\n                if (s[i] == \'#\') {\n                    skipS++;\n                } else {\n                    skipS--;\n                }\n                i--;\n            }\n\n            while (j >= 0 && (t[j] == \'#\' || skipT > 0)) {\n                if (t[j] == \'#\') {\n                    skipT++;\n                } else {\n                    skipT--;\n                }\n                j--;\n            }\n\n            if ((i >= 0 && j >= 0) && s[i] != t[j]) {\n                return false;\n            }\n            \n            if ((i >= 0) != (j >= 0)) {\n                return false;\n            }\n            i--;\n            j--;\n        }\n\n        return true;\n    }\n};\n\n```
['Two Pointers', 'String', 'Stack', 'Simulation', 'C++']