FAANG Onsite Interview Problem - Solution - C++ - O(N)
My friend was asked from one of the FAANG companies.\n\nLogic & Algo\nWe will check all the cases where it should return false, if none matches then we will ret
My friend was asked from one of the FAANG companies.\n\n**Logic & Algo**\nWe will check all the cases where it should return false, if none matches then we will return true.\nWe will use two pointers, one for start (say, iS), and one for end(say, iE).\nWe will move iS and iE till they are pointing at \'X\'.\nNow, if iS and iE are pointing to different values, then we can never reach to the end from the start, hence, return false.\nIf it matches:\n* \tif they are pointing to \'R\', then iS must be less than or equal to iE, as R can be moved to right only from start.\n* \tif they are pointing to \'L\', then iS must be greater than or equal to iE, as L can be moved to left only from start.\n* \tIf the above fails, then we will return false.\n\nAs we will reach the end, there must not remain any L or R in any of the start or end remaining strings.\n\n**Code**\n```\nclass Solution {\npublic:\n    bool canTransform(string start, string end) {\n        int iS = 0, iE = 0;\n        while(iS < start.size() && iE < end.size()){\n            if(start[iS] != \'X\' && end[iE] != \'X\'){\n                if(start[iS] != end[iE])\n                    return false;\n                else if(start[iS] == \'R\' && iS > iE)\n                    return false;\n                else if(start[iS] == \'L\' && iS < iE)\n                    return false;\n                iS++;\n                iE++;\n            }\n            else{\n                if(start[iS] == \'X\')\n                    iS++;\n                else\n                    iE++;\n            }\n        }\n        while(iS < start.size()){\n            if(start[iS] != \'X\')\n                return false;\n            iS++;\n        }\n        while(iE < end.size()){\n            if(end[iE] != \'X\')\n                return false;\n            iE++;\n        }\n        return true;\n    }\n};\n```\n\nPlease upvote and share your feedback.
['C']