two pointers comparing ✅ 14ms, 41.16MB
\n\n# Intuition\nI came up with two approaches, one is to count prefixSum and suffixSum of L and R. For example L we need suffixSum at each index that target ha
![image.png](https://assets.leetcode.com/users/images/819261f1-ce9d-45bd-bd6b-9bcd640f8eec_1733393337.5793726.png)\n\n# Intuition\nI came up with two approaches, one is to count prefixSum and suffixSum of `L` and `R`. For example `L` we need suffixSum at each index that target has less `L` than original. (So original has enough L to move to left.) When encountering `R` the suffixSum needs to reset to 0. It seems doable but after several testing, I can\'t pass all tests so I gave up.\n\nAnother solution is to use two pointers to compare strings directly, which is much easier to implement and more effecient.\n\n# Approach\nInitialize two pointers for the two strings, iterate within their range:\n```\n        val n = start.length\n        var i = 0\n        var j = 0\n        while (i < n && j < n) {\n```\nWhen encountering `_` we just skip it, for both strings. Because we only care about `L` and `R` and their positions.\n```\n            if (start[i] == \'_\') {\n                i++\n                continue\n            }\n            if (target[j] == \'_\') {\n                j++\n                continue \n            }\n```\nAfter skipping spaces, there are 3 invalid cases, we can directly return false:\n- pointers meet different letters: it\'s impossible to make their current letters same\n- pointers meet `L`, but `i < j`: `L` can only move to left, but i is already at left of j, it\'s impossible to move\n- pointers meet `R`, but `i > j`: `R` can only move to right, but i is already at right of j, it\'s impossible to move\n```\n            if (start[i] != target[j] || \n                start[i] == \'L\' && i < j || \n                start[i] == \'R\' && i > j) return false\n```\notherwise increase both pointers:\n```\n            i++\n            j++\n```\nWhen at least one pointer reaches the end, if the other string still has spaces, skip spaces.\n```\n        while (i < n && start[i] == \'_\') i++\n        while (j < n && target[j] == \'_\') j++\n```\nOnly if two pointers stop at the same position (`n`) it\'s a valid case.\n```\n        return i == j\n```\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```kotlin []\nclass Solution {\n    fun canChange(start: String, target: String): Boolean {\n        val n = start.length\n        var i = 0\n        var j = 0\n        while (i < n && j < n) {\n            if (start[i] == \'_\') {\n                i++\n                continue\n            }\n            if (target[j] == \'_\') {\n                j++\n                continue \n            }\n            if (start[i] != target[j] || start[i] == \'L\' && i < j || start[i] == \'R\' && i > j) return false\n            i++\n            j++\n        }\n        while (i < n && start[i] == \'_\') i++\n        while (j < n && target[j] == \'_\') j++\n        return i == j\n    }\n}\n```
['Two Pointers', 'String', 'Kotlin']