Simple Java O(n) solution with O(1) space with explanation
The problem states that cars cannot collide while moving from one position to the other. Hence if we remove the empty lanes both the start and end would look li
The problem states that cars cannot collide while moving from one position to the other. Hence if we remove the empty lanes both the start and end would look like identical. For Example : \nstart -> `RXXL` end -> `XRXL`. Both of the strings are identical if we remove the empty lanes -> `RL`. This is because no two cars exchange their relative position. Thus the final result is to find whether both the lanes after removing the empty lanes looks identical and the index in the end is either left or right with respect to the start positions.\n\nFor Example : \n`XXRXXL` -> `XRXXL` would be invalid because istead of movig right the first car has moved left.\n\nTo achieve this we use two pointers one poiting the car in the source lane and another in the target lane. For every car in the soure lane we check the next car in the target lane and if it is  not positioned with the given conditions we return false.\n\nTime Complexity : `O(n)`\nWe do Atmost 2 * n number of operations.\n\nSpace Complexity : `O(1)`\nWe only use constant space for the pointers and static variables for storing the \'L\', \'R\' and \'X\'.\n\n```\nclass Solution {\n    private static char EMPTY = \'X\';\n    private static char RIGHT = \'R\';\n    private static char LEFT = \'L\';\n    public boolean canTransform(String start, String end) {\n        int len = start.length();\n        if (end.length() != len) {\n            return false;\n        }\n        int endPointer = 0;\n        for (int index = 0; index < len; index++) {\n            char c = start.charAt(index);\n            if (c != EMPTY) {\n                while (endPointer < len && end.charAt(endPointer) == EMPTY){//pointing to the next car in the target lane\n                    endPointer++;\n                }\n                if (endPointer == len) {//insufficient number of  cars in the target// we ran out of cars to match the source lane\n                    return false;\n                }\n                if (c != end.charAt(endPointer) || c == RIGHT && endPointer < index || c == LEFT && endPointer > index) {\n                    return false;\n                }\n                endPointer++;\n            }\n        }\n        while (endPointer < len){\n            if (end.charAt(endPointer) != EMPTY) {//excess cars in the target lane\n                return false;\n            }\n            endPointer++;\n        }\n        return true;\n    }\n}\n```
['Two Pointers']