✅10 line simple C++🎯Beats 95%⏰θ(2n)✅sp:O(1)
Intuition\n Describe your first thoughts on how to solve this problem. \nTo compare the L&R characters of both string for their count of characters and order of
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo compare the L&R characters of both string for their count of characters and order of occurances using 2 pointers.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nBegin with two pointers for target and start string as i and j respectively. The \'_\' can be ignored as we only need to compare the character order and occurances.\n\nLoop through the target string and if an L/R is encountered, loop and obtain the next L/R character occurance in the start string by ignoring the \'_\'.\n\nWhen both pointers are pointing to the corresponding i-th L/R in the string check for the following conditions. All these conditions will make the start string impossible to shape shift to target string:\n\n1. If start string has no more L/R char even though the target has more.\n2. If the char of target doesn\'t match the corresponding char of start.\n    `target[i] != start[j]`\n\n3. If both pointers are at \'L\' and start pointer j is less than target pointer i indicates that target \'L\' is positioned at the right side of start. Since L can\'t move towards right we return False.\n    `start[j]==\'L\' && j<i`\n\n4. If both pointers are at \'R\' and start pointer j is greater than target pointer i indicates that target \'R\' is positioned at the left side of start. Since R can\'t move towards left we return `false`.\n\n    `start[j]==\'R\' && i<j`\n\n- *Final check:*\nIf the start string passed the above loop without returning `false` it\'s time for the final check. As the target string contains no more L/R, check if start contains any additional L/R which makes that can make the frequency count of characters in both the string imbalanced.\n    \n        while(j<target.size()) \n            if(start[j++]!=\'_\') \n                return false;\n\n\n# Complexity\n- Time complexity: $$\u03B8(2n) = O(n)$$\n- Space complexity: $$O(1)$$\n\n\n```cpp []\nclass Solution {\npublic:\n    bool canChange(string start, string target) {\n\n        // line#1: start string pointer\n        int j=0;\n\n        // line#2: Iterate the target string with i as pointer\n        for(int i=0;i<target.size();i++){\n\n            // We only need L & R positions of both string so:\n\n            // line#3: Ignore the \'_\' in target string\n            if (target[i]==\'_\') continue;\n            // line#4: Ignore the \'_\' in start string\n            while (j<target.size() && start[j]==\'_\') j++;\n\n            // line#5: Ifc onditions of the impossibilities:\n\n            // 1. If start string gets exhausted even \n            if(j>=target.size() || \n            // 2. If the order of LR doesn\'t match\n            start[j]!=target[i] || \n            // 3. L can\'t be shifted forward \n            (start[j]==\'L\' && j<i) || \n            // 4. R can\'t be shifted backward\n            (start[j]==\'R\' && j>i) ) \n                return false;\n\n            // line#6: Increase the start pointer\n            j++;\n        }\n\n        // line#7: Check if start string has any extra LR \n        while(j<target.size()) \n            if(start[j++]!=\'_\') \n                return false;\n        \n        // line#8: \n        return true;\n    }\n};\n```\n\n```python []\nclass Solution:\n    def canChange(self, start: str, target: str) -> bool:\n        # line#1 \n        j=0\n        # line#2 \n        for i in range(len(target)):\n            # line#3\n            if target[i]=="_":  continue\n\n            # line#4\n            while j<len(start) and start[j]=="_":  j+=1\n            \n            # line#5\n            if j>=len(start) or start[j]!=target[i] or (start[j]=="L" and i>j) or (start[j]=="R" and j>i): \n                return False\n\n            # line#6\n            j+=1\n        \n        # line#7\n        while(j<len(start)):\n            if start[j]!="_":\n                return False\n            # line#8\n            j+=1\n\n        # line#9\n        return True\n```\n
['Two Pointers', 'String', 'C++', 'Python3']