🔥Stack & 🔥3-Two Pointer🔥| Java | C++ | Python | JavaScript |
There are several approaches to solve this problem, arranged from naive to efficient:\n\n## 1. Naive Approach (Stacks):\n   - One straightforward approach is to
There are several approaches to solve this problem, arranged from naive to efficient:\n\n## 1. **Naive Approach (Stacks):**\n   - One straightforward approach is to simulate the typing process using two stacks. You can iterate through both strings and push characters onto the stacks or pop from the stacks when you encounter a backspace. Then, compare the contents of the two stacks.\n\n\n## 2. **Two-Pointer Approach (Two-Pointer):**\n   - You can use two pointers to compare the strings. Start from the end of both strings and move backwards, skipping characters as you encounter backspaces. Then, compare the characters at the current positions.\n\n\n## 3. **Optimized Two-Pointer Approach (Two-Pointer):**\n   - An improvement on the two-pointer approach is to keep track of the number of backspaces encountered and use this to skip characters efficiently without checking the entire string.\n\n\n## 4. **Reverse and Compare (Two-Pointer):**\n   - Reverse both input strings, and then compare them character by character, skipping characters as needed. This approach doesn\'t require extra space.\n\n\nThe last three approaches mentioned are more efficient than the stack-based approach and have the same time complexity. The optimized two-pointer approach is generally the most efficient, as it doesn\'t require reversing the strings and has a similar time complexity to the other two-pointer approach.\n\n# 1st Method :- Naive Approach (Stack)\uD83D\uDE80\n\n## \u2712\uFE0FCode\n``` Java []\nclass Solution {\n    public boolean backspaceCompare(String s, String t) {\n        // Use stacks to simulate the typing process\n        Stack<Character> stackS = new Stack<>();\n        Stack<Character> stackT = new Stack<>();\n\n        // Process string S\n        for (char c : s.toCharArray()) {\n            if (c != \'#\') {\n                stackS.push(c);  // Push character onto the stack\n            } else if (!stackS.isEmpty()) {\n                stackS.pop();  // Pop if it\'s a backspace and the stack is not empty\n            }\n        }\n\n        // Process string T\n        for (char c : t.toCharArray()) {\n            if (c != \'#\') {\n                stackT.push(c);  // Push character onto the stack\n            } else if (!stackT.isEmpty()) {\n                stackT.pop();  // Pop if it\'s a backspace and the stack is not empty\n            }\n        }\n\n        // Compare the contents of the two stacks\n        return stackS.equals(stackT);\n    }\n}\n```\n``` C++ []\nclass Solution {\n    // Function to check if two strings are equal after applying backspaces\n public :\n    bool backspaceCompare(string s, string t) {\n        // Helper function to process the input string and return the final string after backspacing\n        auto processString = [](string str) {\n            stack<char> result; // Create a stack to store characters\n\n            for (char c : str) {\n                if (c != \'#\') {\n                    result.push(c); // Push non-backspace characters onto the stack\n                } else if (!result.empty()) {\n                    result.pop(); // Pop a character from the stack when encountering a backspace\n                }\n            }\n\n            string finalStr;\n            while (!result.empty()) {\n                finalStr = result.top() + finalStr; // Reconstruct the final string by reversing the stack\n                result.pop();\n            }\n\n            return finalStr; // Return the processed string\n        };\n\n        string processedS = processString(s); // Process the first input string\n        string processedT = processString(t); // Process the second input string\n\n        return processedS == processedT; // Compare the processed strings for equality\n    }\n};\n```\n``` Python []\nclass Solution(object):\n    def backspaceCompare(self, s, t):\n        # Helper function to process the input string and return the final result\n        def process_string(s):\n            stack = []  # Create an empty stack to simulate the typing process\n            for char in s:\n                if char != \'#\':\n                    stack.append(char)  # Push non-backspace characters onto the stack\n                elif stack:\n                    stack.pop()  # Pop from the stack when a backspace is encountered\n            return \'\'.join(stack)  # Convert the stack to a string and return\n\n        # Process both input strings using the helper function\n        processed_S = process_string(s)\n        processed_T = process_string(t)\n\n        # Compare the processed strings to check if they are equal\n        return processed_S == processed_T\n```\n``` JavaScript []\n\nvar backspaceCompare = function(s, t) {\n    // Helper function to apply backspaces and return the final string\n    function processBackspaces(str) {\n        const stack = [];\n        \n        for (let char of str) {\n            if (char === \'#\') {\n                // If a backspace is encountered, pop the last character from the stack\n                if (stack.length > 0) {\n                    stack.pop();\n                }\n            } else {\n                // If a regular character is encountered, push it onto the stack\n                stack.push(char);\n            }\n        }\n        \n        // Convert the stack to a string and return it\n        return stack.join(\'\');\n    }\n\n    // Process both input strings to get the final strings after backspaces\n    const processedS = processBackspaces(s);\n    const processedT = processBackspaces(t);\n\n    // Compare the processed strings to determine if they are equal\n    return processedS === processedT;\n}\n```\n## Complexity \n#### \uD83D\uDEA9Time complexity: O(N + M)\n- The algorithm processes both input strings in a single pass, character by character.\n- In the worst case, it iterates through both strings, which have lengths of `N` and `M`, respectively.\n- Therefore, the time complexity of this algorithm is O(N + M), where `N` and `M` are the lengths of the input strings S and T.\n\n#### \uD83D\uDEA9Space complexity: O(N + M)\n- The space complexity is determined by the space used for the two stacks to store characters.\n- In the worst case, the size of the stacks can be as large as the input strings, so the space complexity is O(N + M).\n- Additionally, there is some constant space used for variables and the string-to-char array conversion, but this is typically negligible compared to the stack space.\n- Therefore, the space complexity is O(N + M), where `N` and `M` are the lengths of the input strings S and T.\n\n![vote.jpg](https://assets.leetcode.com/users/images/5d7623dd-5f82-4343-9f36-dda7fef3f6bf_1697693893.837283.jpeg)\n\n---\n# 2nd Method :- Two-Pointer Approach\uD83D\uDE80\n\n## \u2712\uFE0FCode\n``` Java []\nclass Solution {\n    public boolean backspaceCompare(String s, String t) {\n        // Call the findActualCharIndex function with the provided parameters\n        int ptrS = findActualCharIndex(s, s.length() - 1);\n        int ptrT = findActualCharIndex(t, t.length() - 1);\n\n        while (ptrS >= 0 || ptrT >= 0) {\n            // Find the actual character indices for both strings\n            ptrS = findActualCharIndex(s, ptrS);\n            ptrT = findActualCharIndex(t, ptrT);\n\n            // Check if we have reached the beginning of one of the strings\n            if (ptrS < 0 && ptrT < 0) {\n                return true; // Both strings are equal after backspacing\n            }\n\n            // Compare the characters at the current indices\n            if (ptrS < 0 || ptrT < 0 || s.charAt(ptrS) != t.charAt(ptrT)) {\n                return false; // Characters are not equal, or one string reached its beginning\n            }\n\n            // Move to the previous character in both strings\n            ptrS--;\n            ptrT--;\n        }\n\n        // Both strings are equal after backspacing\n        return true;\n    }\n\n    // Helper function to find the actual character at a given index after considering backspaces\n    // It returns the index of the first non-backspace character in the string.\n    private int findActualCharIndex(String str, int index) {\n        int backspaceCount = 0;\n        while (index >= 0) {\n            if (str.charAt(index) == \'#\') {\n                backspaceCount++;\n            } else if (backspaceCount > 0) {\n                backspaceCount--;\n            } else {\n                break;\n            }\n            index--;\n        }\n        return index;\n    }\n}\n```\n``` C++ []\nclass Solution {\n public :\n    bool backspaceCompare(string s, string t) {\n        int i = s.size() - 1; // Pointer for string s\n        int j = t.size() - 1; // Pointer for string t\n        int skipS = 0;        // Count of backspaces encountered in s\n        int skipT = 0;        // Count of backspaces encountered in t\n        \n        while (i >= 0 || j >= 0) {\n            // Skip backspaces in string s\n            while (i >= 0) {\n                if (s[i] == \'#\') {\n                    skipS++;\n                    i--;\n                } else if (skipS > 0) {\n                    skipS--;\n                    i--;\n                } else {\n                    break;\n                }\n            }\n            \n            // Skip backspaces in string t\n            while (j >= 0) {\n                if (t[j] == \'#\') {\n                    skipT++;\n                    j--;\n                } else if (skipT > 0) {\n                    skipT--;\n                    j--;\n                } else {\n                    break;\n                }\n            }\n            \n            // Compare characters at the current positions\n            if (i >= 0 && j >= 0 && s[i] != t[j]) {\n                return false;\n            }\n            \n            // If one string reaches the beginning and the other doesn\'t, they can\'t be equal\n            if ((i >= 0) != (j >= 0)) {\n                return false;\n            }\n            \n            // Move to the previous character\n            i--;\n            j--;\n        }\n        \n        // Both strings match after handling backspaces\n        return true;\n    }\n};\n```\n``` Python []\nclass Solution(object):\n    def backspaceCompare(self, s, t):\n        def apply_backspace(string):\n            # Helper function to apply backspaces and return the resulting string\n            result = []\n            for char in string:\n                if char != \'#\':\n                    result.append(char)\n                elif result:\n                    result.pop()  # Remove the last character if a backspace is encountered\n            return \'\'.join(result)\n\n        return apply_backspace(s) == apply_backspace(t)\n\n\n```\n``` JavaScript []\n\nvar backspaceCompare = function(s, t) {\n    // Helper function to find the next valid character given a position and string\n    function getNextValidChar(s, index) {\n        let backspaceCount = 0;\n        \n        // Traverse the string backward, counting backspaces and skipping characters\n        while (index >= 0) {\n            if (s[index] === \'#\') {\n                backspaceCount++;\n                index--;\n            } else if (backspaceCount > 0) {\n                backspaceCount--;\n                index--;\n            } else {\n                break;\n            }\n        }\n        \n        return index;\n    }\n    \n    let i = s.length - 1;  // Start from the end of s\n    let j = t.length - 1;  // Start from the end of t\n    \n    while (i >= 0 || j >= 0) {\n        // Find the next valid characters in both strings\n        i = getNextValidChar(s, i);\n        j = getNextValidChar(t, j);\n        \n        // If one string has characters remaining and the other doesn\'t, they are not equal\n        if ((i >= 0 && j < 0) || (i < 0 && j >= 0)) {\n            return false;\n        }\n        \n        // Compare the characters at the current positions\n        if (s[i] !== t[j]) {\n            return false;\n        }\n        \n        // Move to the previous character in both strings\n        i--;\n        j--;\n    }\n    \n    // Both strings are equal after processing backspaces\n    return true;\n}\n```\n## Complexity \n#### \uD83D\uDEA9Time complexity: O(N)\nThe time complexity of this solution is O(N), where N is the length of the longer input string among `s` and `t`. The reason for this is that the algorithm processes each character of both strings once, and the while loop runs until both pointers have reached the beginning of their respective strings.\n\n#### \uD83D\uDEA9Space complexity: O(1)\nThe space complexity of this solution is O(1) because it uses a constant amount of extra space regardless of the input string lengths. The only extra space used is for variables and loop counters, and it doesn\'t depend on the size of the input strings.\n\n![vote.jpg](https://assets.leetcode.com/users/images/db826e05-4fc8-4c82-8b38-06b276e804ff_1697694239.7803414.jpeg)\n\n---\n# 3rd Method :- Optimized Two-Pointer Approach\uD83D\uDE80\n\n## \u2712\uFE0FCode\n``` Java []\nclass Solution {\n    public boolean backspaceCompare(String s, String t) {\n        int i = s.length() - 1;\n        int j = t.length() - 1;\n        int backspaceCountS = 0;\n        int backspaceCountT = 0;\n\n        while (i >= 0 || j >= 0) {\n            // Find the position of the next valid character in s after considering backspaces\n            while (i >= 0 && (s.charAt(i) == \'#\' || backspaceCountS > 0)) {\n                if (s.charAt(i) == \'#\') {\n                    backspaceCountS++;\n                } else {\n                    backspaceCountS--;\n                }\n                i--;\n            }\n\n            // Find the position of the next valid character in t after considering backspaces\n            while (j >= 0 && (t.charAt(j) == \'#\' || backspaceCountT > 0)) {\n                if (t.charAt(j) == \'#\') {\n                    backspaceCountT++;\n                } else {\n                    backspaceCountT--;\n                }\n                j--;\n            }\n\n            if (i < 0 && j < 0) {\n                // Both strings have no more valid characters, they match.\n                return true;\n            }\n\n            if (i < 0 || j < 0 || s.charAt(i) != t.charAt(j)) {\n                // If the valid characters at the current positions don\'t match, the strings are not equal.\n                return false;\n            }\n\n            i--;\n            j--;\n        }\n\n        // If both strings are empty or only contain backspaces, they are considered equal.\n        return true;\n    }\n}\n```\n\n## Complexity \n#### \uD83D\uDEA9Time complexity: O(M + N)\n- Here, M is the length of string `s`, and N is the length of string `t`.\n- The code uses two pointers, one for each string (`i` for `s` and `j` for `t`), and it iterates through both strings once.\n- During the iteration, it handles backspaces by skipping characters, but each character in both strings is visited at most once.\n- Therefore, the time complexity is O(M + N).\n\n#### \uD83D\uDEA9Space complexity: O(1)\n- The code uses a constant amount of extra space to store integer variables (`i`, `j`, `backspaceCountS`, and `backspaceCountT`) and a few integer constants.\n- It doesn\'t use any additional data structures like arrays or lists.\n- As a result, the space complexity is O(1), meaning it\'s constant and not dependent on the input size.\n\n![vote.jpg](https://assets.leetcode.com/users/images/1d2ebea4-4a96-42f9-b430-7ad461aae22b_1697695487.1538076.jpeg)\n\n---\n# 4th Method :- Reverse and Compare (Two-Pointer)\uD83D\uDE80\n\n## \u2712\uFE0FCode\n``` Java []\npublic class Solution {\n    public boolean backspaceCompare(String s, String t) {\n        // Helper function to reverse a string\n        String reversedS = reverseString(s);\n        String reversedT = reverseString(t);\n\n        int i = 0; // Pointer for reversedS\n        int j = 0; // Pointer for reversedT\n\n        while (i < reversedS.length() || j < reversedT.length()) {\n            // Skip backspaces in reversedS\n            int backspacesS = 0;\n            while (i < reversedS.length() && (reversedS.charAt(i) == \'#\' || backspacesS > 0)) {\n                if (reversedS.charAt(i) == \'#\') {\n                    backspacesS++;\n                } else {\n                    backspacesS--;\n                }\n                i++;\n            }\n\n            // Skip backspaces in reversedT\n            int backspacesT = 0;\n            while (j < reversedT.length() && (reversedT.charAt(j) == \'#\' || backspacesT > 0)) {\n                if (reversedT.charAt(j) == \'#\') {\n                    backspacesT++;\n                } else {\n                    backspacesT--;\n                }\n                j++;\n            }\n\n            // Compare characters\n            if (i < reversedS.length() && j < reversedT.length()) {\n                if (reversedS.charAt(i) != reversedT.charAt(j)) {\n                    return false;\n                }\n                i++;\n                j++;\n            } else if (i < reversedS.length() || j < reversedT.length()) {\n                // One of the strings reached the end while the other didn\'t\n                return false;\n            }\n        }\n\n        return true;\n    }\n\n    private String reverseString(String s) {\n        // Helper function to reverse a string\n        StringBuilder reversed = new StringBuilder();\n        for (int i = s.length() - 1; i >= 0; i--) {\n            reversed.append(s.charAt(i));\n        }\n        return reversed.toString();\n    }\n\n\n}\n```\n``` C++ []\nclass Solution {\npublic:\n    bool backspaceCompare(string s, string t) {\n        int i = s.size() - 1;      // Start at the end of string s.\n        int j = t.size() - 1;      // Start at the end of string t.\n        int backspaceCountS = 0;   // Counter for backspaces in s.\n        int backspaceCountT = 0;   // Counter for backspaces in t.\n\n        // Iterate while there are characters in either s or t to compare.\n        while (i >= 0 || j >= 0) {\n            // Handle backspaces and character comparisons for string s.\n            while (i >= 0 && (s[i] == \'#\' || backspaceCountS > 0)) {\n                if (s[i] == \'#\') {\n                    backspaceCountS++; // Increment backspace counter.\n                    i--;              // Move to the previous character.\n                } else if (backspaceCountS > 0) {\n                    backspaceCountS--; // Decrement backspace counter.\n                    i--;              // Move to the previous character.\n                }\n            }\n\n            // Handle backspaces and character comparisons for string t.\n            while (j >= 0 && (t[j] == \'#\' || backspaceCountT > 0)) {\n                if (t[j] == \'#\') {\n                    backspaceCountT++; // Increment backspace counter.\n                    j--;              // Move to the previous character.\n                } else if (backspaceCountT > 0) {\n                    backspaceCountT--; // Decrement backspace counter.\n                    j--;              // Move to the previous character.\n                }\n            }\n\n            // Compare characters if both s and t have characters to compare.\n            if (i >= 0 && j >= 0 && s[i] != t[j]) {\n                return false; // If characters don\'t match, return false.\n            }\n\n            // Check for the case where one string still has characters while the other doesn\'t.\n            if ((i >= 0 && j < 0) || (j >= 0 && i < 0)) {\n                return false; // Inequality because one string is longer.\n            }\n\n            i--; // Move to the previous character in s.\n            j--; // Move to the previous character in t.\n        }\n\n        return true; // Both strings are equal after backspaces.\n    }\n};\n\n```\n``` Python []\nclass Solution(object):\n    def backspaceCompare(self, s, t):\n        # Helper function to get the final string after applying backspaces\n        def get_final_string(s):\n            result = []\n            for char in s:\n                if char != \'#\':\n                    result.append(char)\n                elif result:  # Check if there\'s a character to remove\n                    result.pop()\n            return \'\'.join(result)\n\n        # Get the final strings for s and t\n        final_S = get_final_string(s)\n        final_T = get_final_string(t)\n\n        # Compare the final strings\n        return final_S == final_T\n\n\n```\n``` JavaScript []\n/**\n * @param {string} s\n * @param {string} t\n * @return {boolean}\n */\n\nvar backspaceCompare = function(s, t) {\n  // Function to reverse the string while taking into account backspaces\n  function reverseWithBackspace(str) {\n    let result = [];\n    let backspaceCount = 0;\n\n    for (let i = str.length - 1; i >= 0; i--) {\n      if (str[i] === \'#\') {\n        backspaceCount++;\n      } else if (backspaceCount > 0) {\n        // If we encounter a non-backspace character with backspaces pending, skip it\n        backspaceCount--;\n      } else {\n        // Add the character to the result\n        result.push(str[i]);\n      }\n    }\n\n    return result.join(\'\');\n  }\n\n  // Reverse both input strings after processing backspaces\n  const reversedS = reverseWithBackspace(s);\n  const reversedT = reverseWithBackspace(t);\n\n  // Compare the reversed strings to check for equality\n  return reversedS === reversedT;\n}\n```\n\n## Complexity \n#### \uD83D\uDEA9Time complexity: O(N)\nThe time complexity is O(N), where N is the length of the longer input string. In the worst case, you may need to iterate through both input strings once, even though you\'re using two pointers and skipping characters due to backspaces.\n\n#### \uD83D\uDEA9Space complexity: O(1)\nThe space complexity is O(1) because the extra space used is constant and doesn\'t depend on the input string lengths. The solution reverses the input strings in-place and uses only a few integer variables (i, j, backspacesS, and backspacesT) to keep track of the pointers and backspace counts.\n\n![upvote.png](https://assets.leetcode.com/users/images/ca967c37-43b7-4c11-88e0-9ebe4d58d4ca_1697695500.0946803.png)\n# Up Vote Guys\n
['Two Pointers', 'Stack', 'Python', 'C++', 'Java', 'JavaScript']