[LeetCode] Swap Adjacent in LR String

Problem: In a string composed of 'L', 'R', and 'X' characters, like "RXXLRXRXL", a move consists of either replacing one occurrence of "XL" with "LX", or replacing one occurrence of "RX" with "XR". Given the starting string start and the ending string end, return True if and only if there exists a sequence of moves to transform one string to the other.

Example:

Input: start = "RXXLRXRXL", end = "XRLXXRRLX"
Output: true
Explanation: We can transform start to end following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

Input: start = "X", end = "L"
Output: false

Input: start = "LLR", end = "RRL"
Output: false

Input: start = "XL", end = "LX"
Output: true

Input: start = "XLLR", end = "LXLX"
Output: false

Approach: First thing to notice is a L can go only to its left side and R can go only to its right so we can treat this question is like there are two type of people standing in a row; 'L' type of people can only move to their left side and 'R' type of people can always move to their right side and they can only move to an empty place 'X' only.

Once we visualize this, first thing we can notice is that people can't cross each other (no empty place). right like cars in a single lane can't overtake. That means if we remove all the 'X's from both start and end strings, the strings should be same.

Second thing to notice is L can only move to its left side. That means if the positions of L in start are SL1, SL2,...,SLn and positions of L in end are EL1, EL2,...ELn then  SL1 >= EL1, SL2 >= EL2, ..., SLn >= ELn.

Similarly we know that R can only move to its right side. That means for all the 'R' positions in start say SR1, SR2,...,SRn  and for all the 'R' positions in end say ER1,ER2,...,ERn, SRi <= ERi must be true where i = 1.2,...number of 'R's.

That's all about the approach. 

Implementation in C#:

    public bool CanTransform(string start, string end) 

    {

        if (start.Length != end.Length)

        {

            return false;

        }

        if (start.Replace("X", string.Empty) != end.Replace("X", string.Empty))

        {

            return false;

        }

        int eLPos = 0;

        int eRPos = 0;

        for (int sItr = 0; sItr < start.Length; ++sItr)

        {

            if(start[sItr] == 'L')

            {

                while (end[eLPos] != 'L')

                {

                    ++eLPos;

                }                

                if (sItr < eLPos++)

                {

                    return false;

                }

            }

            else if (start[sItr] == 'R')

            {

                while (end[eRPos] != 'R')

                {

                    ++eRPos;

                }

                

                if (sItr > eRPos++)

                {

                    return false;

                }

            }

        }   

        return true;

    }

Complexity: O(n)