✅ Easier Than Easy ✅ Multiple Approaches ✅ Beats 100% ✅ O(N) Time  O(1) Space
\n\n# YouTube Video Explanation\nhttps://youtu.be/AANUkU-FVqc\n\n\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making comp
![Screenshot 2023-10-19 100510.png](https://assets.leetcode.com/users/images/90127a0b-b231-4d8d-824f-6b596fdf765a_1697690230.8453283.png)\n\n# YouTube Video Explanation\n[https://youtu.be/AANUkU-FVqc](https://youtu.be/AANUkU-FVqc)\n\n\uD83D\uDD25 ***Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.***\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n***Subscribe Goal: 100 Subscribers\nCurrent Subscribers: 84***\n\n## Intution:\nThe "Backspace String Compare" problem presents us with two strings, `s` and `t`, which contain lowercase letters and the \'#\' character. We need to determine if these strings are equal when typed into empty text editors that support backspace typing.\n\n## Approach 1 - Brute Force (Using Stacks):\nWe can start with a straightforward approach. We\'ll utilize two stacks, `s1` and `s2`, to simulate typing both strings into text editors that handle backspace. We iterate through the strings, handling backspaces when we encounter the \'#\' character. After processing, we construct the resulting strings `res1` and `res2` from the stacks. If these strings are equal, we return `true`, indicating that the original strings are equivalent.\n\nHere\'s the code for this approach:\n\n```java\nclass Solution {\n    public boolean backspaceCompare(String s, String t) {\n        Stack<Character> s1 = new Stack<Character>();\n        Stack<Character> s2 = new Stack<Character>();\n        \n        for(char ch : s.toCharArray()){\n            if(ch == \'#\'){\n                if(!s1.isEmpty())\n                    s1.pop();\n                continue;\n            }\n            s1.push(ch);\n        }\n        \n        for(char ch : t.toCharArray()){\n            if(ch == \'#\'){\n                if(!s2.isEmpty())\n                    s2.pop();\n                continue;\n            }\n            s2.push(ch);\n        }\n        \n        String res1 = "";\n        String res2 = "";\n        \n        while(!s1.isEmpty())\n            res1 += s1.pop();\n        \n        while(!s2.isEmpty())\n            res2 += s2.pop();\n        \n        return res1.equals(res2);\n    }\n}\n```\n\n## Approach 2 - Optimized Solution:\nIn this optimized approach, we avoid constructing temporary strings. Instead, we iterate through the strings in reverse order, taking into account backspaces along the way. The method `nextChar` helps us navigate through the \'#\' characters and calculate the effective position of the next valid character.\n\nHere\'s the code for the optimized approach:\n\n```java\nclass Solution {\n    private static int nextChar(String str, int cur){\n        while(cur > -1 && str.charAt(cur) == \'#\'){\n            int cnt = 1;\n            for(cur--; cur > -1 && cnt > 0; cur--)\n                cnt += str.charAt(cur) == \'#\'? 1 : -1;\n        }\n        return cur;\n    }\n    \n    public boolean backspaceCompare(String s, String t) {\n        int i = nextChar(s, s.length() - 1);\n        int j = nextChar(t, t.length() - 1);\n        \n        while(i > -1 && j > -1){\n            if(s.charAt(i) != t.charAt(j)) return false;\n            i = nextChar(s, i - 1);\n            j = nextChar(t, j - 1);\n        }\n        \n        if(i == -1 && j == -1) return true;\n        return false;\n    }\n}\n```\n\n<iframe src="https://leetcode.com/playground/CDwCd2a7/shared" frameBorder="0" width="600" height="400"></iframe>\n\n## Complexity:\n- The time complexity for both approaches is `O(N)`, where N is the length of the longer of the two input strings, as we iterate through both strings only once.\n\n- Space Complexity if `O(1)` for optimal approach and `O(N)` for stack approack.\n\n---\n\n![upvote1.jpeg](https://assets.leetcode.com/users/images/092446d1-ea3c-45ed-8ac2-f067bffaa098_1697690529.1446989.jpeg)\n
['Two Pointers', 'String', 'Stack', 'Swift', 'Simulation', 'C++', 'Java', 'Ruby', 'JavaScript']