✅ 95.83% Two Pointers & Stack
Intuition\nWhen encountering two strings, s and t, where the character # behaves as a backspace, our immediate reaction is to understand the final form of each 
# Intuition\nWhen encountering two strings, `s` and `t`, where the character `#` behaves as a backspace, our immediate reaction is to understand the final form of each string after applying all the backspaces. If the post-processed strings match, they are equivalent. One way to address this is to emulate the keystrokes for each string: when a character isn\'t `#`, we "type" it out; if it is `#`, it leads to the "deletion" of the preceding character.\n\n## Live Coding + Explain\nhttps://youtu.be/MLgvNLew0U8?si=35-f5A9LefNs7p4_\n\n# Approach 1: Two Pointers\n1. **Processing the String**: To emulate the "typing" and "erasing" action, we navigate through each string with two pointers. The main pointer (`i`) traverses each character, while the auxiliary pointer (`k` for `s` and `p` for `t`) indicates the effective position of the last character post backspaces.\n   - If the character at the main pointer isn\'t `#`, it\'s "typed" at the location of the auxiliary pointer, which is then incremented.\n   - If the character is `#`, the preceding character is "erased" by decrementing the auxiliary pointer.\n   - The concluding value of the auxiliary pointer after processing gives the effective string length after considering backspaces.\n\n2. **Comparing the Strings**: After processing, the effective lengths (final values of `k` and `p`) are compared. A difference in lengths directly implies the strings aren\'t equal. If the lengths align, a character-by-character comparison is performed up to their effective lengths.\n\n### Pros\n- This approach is space efficient since it uses a constant amount of space.\n- Directly manipulates the input strings without creating new ones.\n\n### Cons\n- Might be a bit harder to conceptualize for someone unfamiliar with the two-pointer technique.\n\n# Approach 2: Using Stack\nThe idea here is to use the inherent nature of stacks to simulate the backspace operation.\n1. Iterate through each character of the string.\n2. If the character isn\'t `#`, it\'s pushed onto the stack.\n3. If the character is `#` and the stack isn\'t empty, the top element (last typed character) is popped (i.e., "erased").\n4. After processing, the contents of the stacks for both strings are compared.\n\n### Pros\n- More intuitive and straightforward. The stack naturally provides the "last in, first out" behavior which is handy for this problem.\n- Easier to implement.\n\n### Cons\n- Uses extra space (although linear) to store characters in the stack.\n\n# Complexity\n\nFor both approaches:\n- **Time complexity**: $O(n)$ - Both strings are traversed once, where $n$ is the total length of the strings `s` and `t`.\n\nFor the two-pointer approach:\n- **Space complexity**: $O(1)$ - Only a fixed amount of space is used for pointers and for converting strings to lists for in-place modifications.\n\nFor the stack approach:\n- **Space complexity**: $O(n)$ - In the worst case, if there are no backspaces, the entire string might be stored in the stack.\n\n# Code (Using Two Pointers)\n``` Python []\nclass Solution:\n    def backspaceCompare(self, s: str, t: str) -> bool:\n        \n        def process_string(string):\n            k = 0\n            for i in range(len(string)):\n                if string[i] != \'#\':\n                    string[k] = string[i]\n                    k += 1\n                else:\n                    k = max(k-1, 0)\n            return k\n        \n        # Convert strings to lists for in-place modifications\n        s, t = list(s), list(t)\n        \n        k = process_string(s)\n        p = process_string(t)\n        \n        # If effective lengths are different, return False\n        if k != p:\n            return False\n        \n        # Compare the effective characters\n        for i in range(k):\n            if s[i] != t[i]:\n                return False\n        \n        return True\n```\n``` C++ []\nclass Solution {\npublic:\n    bool backspaceCompare(string s, string t) {\n        int k = processString(s);\n        int p = processString(t);\n\n        if (k != p) return false;\n\n        for (int i = 0; i < k; i++) {\n            if (s[i] != t[i]) return false;\n        }\n\n        return true;\n    }\n\nprivate:\n    int processString(string& str) {\n        int k = 0;\n        for (char c : str) {\n            if (c != \'#\') {\n                str[k++] = c;\n            } else if (k > 0) {\n                k--;\n            }\n        }\n        return k;\n    }\n};\n```\n``` Java []\npublic class Solution {\n    public boolean backspaceCompare(String S, String T) {\n        char[] sChars = S.toCharArray();\n        char[] tChars = T.toCharArray();\n        \n        int k = processString(sChars);\n        int p = processString(tChars);\n\n        if (k != p) return false;\n\n        for (int i = 0; i < k; i++) {\n            if (sChars[i] != tChars[i]) return false;\n        }\n\n        return true;\n    }\n\n    private int processString(char[] chars) {\n        int k = 0;\n        for (char c : chars) {\n            if (c != \'#\') {\n                chars[k++] = c;\n            } else if (k > 0) {\n                k--;\n            }\n        }\n        return k;\n    }\n}\n```\n``` Go []\nfunc backspaceCompare(S string, T string) bool {\n    sRunes := []rune(S)\n    tRunes := []rune(T)\n    k := processString(sRunes)\n    p := processString(tRunes)\n\n    if k != p {\n        return false\n    }\n\n    for i := 0; i < k; i++ {\n        if sRunes[i] != tRunes[i] {\n            return false\n        }\n    }\n\n    return true\n}\n\nfunc processString(chars []rune) int {\n    k := 0\n    for _, c := range chars {\n        if c != \'#\' {\n            chars[k] = c\n            k++\n        } else if k > 0 {\n            k--\n        }\n    }\n    return k\n}\n```\n``` Rust []\nimpl Solution {\n    pub fn backspace_compare(s: String, t: String) -> bool {\n        let mut s_chars: Vec<char> = s.chars().collect();\n        let mut t_chars: Vec<char> = t.chars().collect();\n        \n        let k = Self::process_string(&mut s_chars);\n        let p = Self::process_string(&mut t_chars);\n\n        if k != p {\n            return false;\n        }\n\n        for i in 0..k {\n            if s_chars[i] != t_chars[i] {\n                return false;\n            }\n        }\n\n        true\n    }\n\n    fn process_string(chars: &mut Vec<char>) -> usize {\n        let chars_copy = chars.clone();\n        let mut k = 0;\n        for &c in chars_copy.iter() {\n            if c != \'#\' {\n                chars[k] = c;\n                k += 1;\n            } else if k > 0 {\n                k -= 1;\n            }\n        }\n        k\n    }\n}\n```\n``` JavaScript []\nvar backspaceCompare = function(S, T) {\n    let sChars = S.split(\'\');\n    let tChars = T.split(\'\');\n    \n    let k = processString(sChars);\n    let p = processString(tChars);\n\n    if (k !== p) return false;\n\n    for (let i = 0; i < k; i++) {\n        if (sChars[i] !== tChars[i]) return false;\n    }\n\n    return true;\n};\n\nfunction processString(chars) {\n    let k = 0;\n    for (let c of chars) {\n        if (c !== \'#\') {\n            chars[k++] = c;\n        } else if (k > 0) {\n            k--;\n        }\n    }\n    return k;\n}\n```\n``` PHP []\nclass Solution {\n\n    /**\n     * @param String $S\n     * @param String $T\n     * @return Boolean\n     */\n    function backspaceCompare($S, $T) {\n        $k = $this->processString($S);\n        $p = $this->processString($T);\n\n        if ($k != $p) return false;\n\n        for ($i = 0; $i < $k; $i++) {\n            if ($S[$i] != $T[$i]) return false;\n        }\n\n        return true;\n    }\n\n    function processString(&$str) {\n        $k = 0;\n        for ($i = 0; $i < strlen($str); $i++) {\n            if ($str[$i] != \'#\') {\n                $str[$k] = $str[$i];\n                $k++;\n            } else if ($k > 0) {\n                $k--;\n            }\n        }\n        return $k;\n    }\n}\n```\n``` C# []\npublic class Solution {\n    public bool BackspaceCompare(string S, string T) {\n        char[] sChars = S.ToCharArray();\n        char[] tChars = T.ToCharArray();\n        \n        int k = ProcessString(sChars);\n        int p = ProcessString(tChars);\n\n        if (k != p) return false;\n\n        for (int i = 0; i < k; i++) {\n            if (sChars[i] != tChars[i]) return false;\n        }\n\n        return true;\n    }\n\n    private int ProcessString(char[] chars) {\n        int k = 0;\n        foreach (char c in chars) {\n            if (c != \'#\') {\n                chars[k++] = c;\n            } else if (k > 0) {\n                k--;\n            }\n        }\n        return k;\n    }\n}\n\n```\n\n## Live Coding Stack\nhttps://youtu.be/S19mL8d1XEo?si=d5ltlzwXjMRKaixW\n\n# Code (Using Stack)\n``` Python\nclass Solution:\n    def backspaceCompare(self, s: str, t: str) -> bool:\n        \n        def process_string(string):\n            stack = []\n            for char in string:\n                if char != \'#\':\n                    stack.append(char)\n                elif stack:\n                    stack.pop()\n            return stack\n        \n        return process_string(s) == process_string(t)\n```\n\n## Performance \n\n| Language | Execution Time (ms) | Memory Usage |\n|----------|---------------------|--------------|\n| Java     | 0 ms                | 41.2 MB      |\n| C++      | 0 ms                | 6.6 MB       |\n| Rust     | 1 ms                | 2 MB         |\n| Go       | 1 ms                | 2 MB         |\n| PHP      | 3 ms                | 18.8 MB      |\n| Python3  | 34 ms               | 16.3 MB      |\n| JavaScript | 53 ms             | 43.1 MB      |\n| C#       | 70 ms               | 38.3 MB      |\n\n![v1.png](https://assets.leetcode.com/users/images/d952d4b0-814e-432a-a4b2-7c754553da59_1697702375.10123.png)\n\n\n# What We Learned\nBy exploring these two approaches, we see the importance of understanding and applying different problem-solving techniques. While both strategies lead to the same solution, they offer different perspectives and trade-offs. The two-pointer technique is a powerful tool, especially for space-constrained problems. On the other hand, using data structures like stacks can simplify problems by leveraging their inherent properties. The choice of approach often depends on the problem\'s constraints and the desired trade-offs between time and space efficiency.
['Two Pointers', 'PHP', 'Simulation', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'JavaScript', 'C#']