(Java Stack) Each 'L' and 'R' in 'start' actually corresponds to each other in 'end'
As the title indicates, each \'L\' and \'R\' in \'start\' should correspond to their counterparts in \'end\'. This is because \'R\' can only move to right blank
As the title indicates, each \'L\' and \'R\' in \'start\' should correspond to their counterparts in \'end\'. This is because \'R\' can only move to right blank space \'X\' (if any) and \'L\' can only move to left blank space \'X\' (if any), and they can\'t \'fly over\' each other (e.g. `RL` can\'t be transformed into `LR`).\n\nKeeping this in mind, take start=`RXXLRXRXL` and end=`XRLXXRRLX` as an example:\n\n1. First \'R\' at index 0 in \'start\' should correspond to the first \'R\' at index 1 in \'end. \'R\' should only move towards right so this step is valid. \'R\' can only move to right so make sure `start.R.index <= end.R.index`\n\n2. Similarly first \'L\' at index 3 in \'start\' corresponds exactly to the first \'L\' at index 2 in \'end\'. It\'s also valid. \'L\' can only move to left so make sure `start.L.index >= end.L.index`.\n\n3. So on so forth...\n\nLet\'s use 2 stacks to indicate this simple mapping and I know this can be optimized :)\n\n```\nclass Solution {\n    class Pos {\n        char c;\n        int index;\n        public Pos(char c, int index) {\n            this.c = c;\n            this.index = index;\n        }\n    }\n    \n    public boolean canTransform(String start, String end) {\n        Deque<Pos> startStack = new ArrayDeque<>();\n        Deque<Pos> endStack = new ArrayDeque<>();\n        \n        for (int i = 0; i < start.length(); i++) {\n            char sc = start.charAt(i);\n            char ec = end.charAt(i);\n            if (sc != \'X\') {\n                startStack.addLast(new Pos(sc, i));\n            }\n            if (ec != \'X\') {\n                endStack.addLast(new Pos(ec, i));\n            }\n        }\n        \n        if (startStack.size() != endStack.size()) {\n            return false;\n        }\n        \n        while (!startStack.isEmpty() && !endStack.isEmpty()) {\n            Pos sPos = startStack.removeLast();\n            Pos ePos = endStack.removeLast();\n            \n            char sc = sPos.c;\n            int sIndex = sPos.index;\n            char ec = ePos.c;\n            int eIndex = ePos.index;\n            \n            if (sc != ec) {\n                return false;\n            }\n            if (sc == \'L\' && sIndex < eIndex || sc == \'R\' && sIndex > eIndex) {\n                return false;\n            }\n        }\n        return startStack.isEmpty() && endStack.isEmpty();\n    }\n}\n```\n\nWith O(n) time and space.
['Stack', 'Java']