【Video】Give me 10 minutes - How we think about a solution - Python, JavaScript, Java, C++
Intuition\nUsing stack or pointers\n\n---\n\n# Solution Video\n\nhttps://youtu.be/YBt2dPL6z5o\n\n\u203B I put my son on my lap and recorded a video, so I\'m fee
# Intuition\nUsing stack or pointers\n\n---\n\n# Solution Video\n\nhttps://youtu.be/YBt2dPL6z5o\n\n\u203B I put my son on my lap and recorded a video, so I\'m feeling a little rushed. lol Please leave a comment if you have any questions.\n\n\u25A0 Timeline of the video\n`0:04` Stack solution code\n`0:23` Explain key point with O(1) space\n`1:12` Consider 4 cases\n`3:14` Coding\n`7:20` Time Complexity and Space Complexity\n\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 2,734\nMy initial goal is 10,000\nThank you for your support!\n\n---\n\n# Approach\n\n## How we think about a solution\n\nSimply, we can solve this question with `stack` like this.\n\n```\nclass Solution:\n    def backspaceCompare(self, s: str, t: str) -> bool:\n\n        def remove_characters(s):\n            stack = []\n            for char in s:\n                if char == \'#\' and stack:\n                    stack.pop()\n                elif char != \'#\':\n                    stack.append(char)\n            return stack\n\n        return remove_characters(s) == remove_characters(t)\n\n```\n\nBut we can improve space complexity to `O(1)`.\n\nWe use `pointers` for s and t but problem is\n\n\n---\n\nWe don\'t know whether we should keep these characters or not. \n\n---\n\nTo solve the problem, my idea is to iterate through both input strings from the end.\n\n---\n\n\u2B50\uFE0F Points\n\nIterate through the both strings from end. In that case, basically\n\nIf we meet alphabets, then we should keep them.\nIf we meet "#", then next character will be removed.\n\n---\n\n- Consider basic 4 cases\n\nI think there are 4 basic cases we should consider.\n\n---\n\n\u2B50\uFE0F Points\n\n1. The case where the same characters remain in the end\n  Example case: `s = "ab#c"` `t = "ad#c"`\n  Results: `true`\n2. The case where we remove all characters at the same time\n  Example case: `s = "ab##"` `t = "c#d#"`\n  Results: `true`\n3. The case where we remove all characters in one input string first, opposite of case 2\n  Example case: `s = "ab#"` `t = "c#d#"`\n  Results: `false`\n4. The case where different characters remain in the end, opposite of case 1\n  Example case: `s = "a#c"` `t = "b"`\n  Results: `false`\n---\n\n### Algorithm Overview:\n- The code is designed to determine whether two strings are equal after applying backspace operations. It compares the two strings character by character after processing the backspace operations.\n\n### Detailed Explanation:\n1. Define a function `get_next_valid_char_index` that takes two arguments: `s` (a string) and `end` (an integer representing the index to start from).\n   - Initialize `backspace_count` to 0.\n   - Start a while loop that runs while `end` is greater than or equal to 0.\n   - Within the loop:\n     - Check if the character at index `end` in string `s` is a \'#\' (backspace).\n     - If it is a \'#\', increment `backspace_count`.\n     - If `backspace_count` is greater than 0, decrement it to simulate the removal of a character.\n     - If neither of the above conditions is met, break out of the loop. This indicates that you\'ve found the next valid character\'s index.\n     - Decrement `end` by 1 in each iteration.\n\n2. Initialize two pointers, `ps` and `pt`, to the last index of strings `s` and `t`, respectively.\n\n3. Enter a while loop that continues as long as `ps` is greater than or equal to 0 or `pt` is greater than or equal to 0. This loop handles the comparison of the processed strings.\n\n4. In each iteration of the loop:\n   - Update `ps` using the `get_next_valid_char_index` function for string `s`.\n   - Update `pt` using the `get_next_valid_char_index` function for string `t`.\n\n5. After both `ps` and `pt` are updated:\n   - If `ps` is less than 0 and `pt` is less than 0, it means both processed strings are empty. In this case, print "aaaaaa" as a debug message (you can remove it) and return `True` as the strings are equivalent after applying backspace operations.\n\n6. If either `ps` or `pt` is less than 0 but not both, it means one of the strings is empty while the other is not. In this case, return `False` as the strings are not equivalent.\n\n7. If neither of the above conditions is met, check if the characters at indices `ps` in string `s` and `pt` in string `t` are not equal. If they are not equal, return `False`.\n\n8. Decrement `ps` and `pt` by 1 to move on to the next character in both strings.\n\n9. Repeat the loop until both strings are fully processed.\n\n10. If none of the conditions for returning `False` are met throughout the loop, it means the strings are equivalent after applying backspace operations, and the function returns `True`.\n\n\n# Complexity\n- Time complexity: $$O(max(len(s), len(t))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n```python []\nclass Solution:\n    def backspaceCompare(self, s: str, t: str) -> bool:\n\n        def get_next_valid_char_index(s, end):\n            backspace_count = 0\n            while end >= 0:\n                if s[end] == \'#\':\n                    # find "#"\n                    backspace_count += 1\n                elif backspace_count > 0:\n                    # find an alphabet but skip it because we have backspaces\n                    backspace_count -= 1\n                else:\n                    # if we don\'t have backspaces and current character is alphabet\n                    # it\'s time to compare two characters from s and t\n                    break\n                end -= 1\n            return end # return current end pointer for the next iteration.\n\n        ps = len(s) - 1\n        pt = len(t) - 1\n\n        while ps >= 0 or pt >= 0:\n            ps = get_next_valid_char_index(s, ps)\n            pt = get_next_valid_char_index(t, pt)\n\n            if ps < 0 and pt < 0:\n                # example case s = "ab##" t = "c#d#", case 2                \n                return True\n            if ps < 0 or pt < 0:\n                # example case s = "ab#" t = "c#d#", case 3\n                return False\n            elif s[ps] != t[pt]:\n                # example case s = "a#c" t = "b", case 4\n                return False\n\n            ps -= 1\n            pt -= 1\n\n        # example case s = "ab#c" t = "ad#c", case 1\n        return True\n```\n```javascript []\n/**\n * @param {string} s\n * @param {string} t\n * @return {boolean}\n */\nvar backspaceCompare = function(s, t) {\n    function get_next_valid_char_index(str, end) {\n        let backspace_count = 0;\n        while (end >= 0) {\n            if (str.charAt(end) === \'#\') {\n                backspace_count++;\n            } else if (backspace_count > 0) {\n                backspace_count--;\n            } else {\n                break;\n            }\n            end--;\n        }\n        return end;\n    }\n\n    let ps = s.length - 1;\n    let pt = t.length - 1;\n\n    while (ps >= 0 || pt >= 0) {\n        ps = get_next_valid_char_index(s, ps);\n        pt = get_next_valid_char_index(t, pt);\n\n        if (ps < 0 && pt < 0) {\n            return true;\n        }\n        if (ps < 0 || pt < 0) {\n            return false;\n        } else if (s.charAt(ps) !== t.charAt(pt)) {\n            return false;\n        }\n\n        ps--;\n        pt--;\n    }\n\n    return true;    \n};\n```\n```java []\nclass Solution {\n    public boolean backspaceCompare(String s, String t) {\n        int ps = s.length() - 1;\n        int pt = t.length() - 1;\n\n        while (ps >= 0 || pt >= 0) {\n            ps = get_next_valid_char_index(s, ps);\n            pt = get_next_valid_char_index(t, pt);\n\n            if (ps < 0 && pt < 0) {\n                return true;\n            }\n            if (ps < 0 || pt < 0) {\n                return false;\n            } else if (s.charAt(ps) != t.charAt(pt)) {\n                return false;\n            }\n\n            ps--;\n            pt--;\n        }\n\n        return true;        \n    }\n\n    private int get_next_valid_char_index(String str, int end) {\n        int backspace_count = 0;\n        while (end >= 0) {\n            if (str.charAt(end) == \'#\') {\n                backspace_count++;\n            } else if (backspace_count > 0) {\n                backspace_count--;\n            } else {\n                break;\n            }\n            end--;\n        }\n        return end;\n    }    \n}\n```\n```C++ []\nclass Solution {\npublic:\n    bool backspaceCompare(string s, string t) {\n        int ps = s.length() - 1;\n        int pt = t.length() - 1;\n\n        while (ps >= 0 || pt >= 0) {\n            ps = get_next_valid_char_index(s, ps);\n            pt = get_next_valid_char_index(t, pt);\n\n            if (ps < 0 && pt < 0) {\n                return true;\n            }\n            if (ps < 0 || pt < 0) {\n                return false;\n            } else if (s[ps] != t[pt]) {\n                return false;\n            }\n\n            ps--;\n            pt--;\n        }\n\n        return true;        \n    }\n\nprivate:\n    int get_next_valid_char_index(string str, int end) {\n        int backspace_count = 0;\n        while (end >= 0) {\n            if (str[end] == \'#\') {\n                backspace_count++;\n            } else if (backspace_count > 0) {\n                backspace_count--;\n            } else {\n                break;\n            }\n            end--;\n        }\n        return end;\n    }    \n};\n```\n\n---\n\nThank you for reading my post.\n\u2B50\uFE0F Please upvote it and don\'t forget to subscribe to my channel!\n\n\u25A0 Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n### My next daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/backspace-string-compare/solutions/4184137/video-give-me-10-minutes-how-we-think-about-a-solution-python-javascript-java-c/\n\nvideo\nhttps://youtu.be/N8QehVXYSc0\n\n\u25A0 Timeline of the video\n`0:04` 2 Keys to solve this question\n`0:18` Explain the first key point\n`0:45` Explain the first key point\n`1:27` Explain the second key point\n`5:44` Coding\n`9:39` Time Complexity and Space Complexity\n\n\n### My previous daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/parallel-courses-iii/solutions/4180474/video-give-me-10-minutes-how-we-think-about-a-solution/\n\nvideo\nhttps://youtu.be/PWorxtrU6hY\n\n\u25A0 Timeline of the video\n`0:04` Key point to solve this question\n`0:23` Explain the first key point\n`1:12` Explain the second key point\n`1:39` Demonstrate real algorithms\n`6:36` Coding\n`10:33` Time Complexity and Space Complexity
['C++', 'Java', 'Python3', 'JavaScript']