<p>In a string composed of <code>&#39;L&#39;</code>, <code>&#39;R&#39;</code>, and <code>&#39;X&#39;</code> characters, like <code>&quot;RXXLRXRXL&quot;</code>, a move consists of either replacing one occurrence of <code>&quot;XL&quot;</code> with <code>&quot;LX&quot;</code>, or replacing one occurrence of <code>&quot;RX&quot;</code> with <code>&quot;XR&quot;</code>. Given the starting string <code>start</code> and the ending string <code>end</code>, return <code>True</code> if and only if there exists a sequence of moves to transform <code>start</code> to <code>end</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> start = &quot;RXXLRXRXL&quot;, end = &quot;XRLXXRRLX&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> We can transform start to end following these steps:
RXXLRXRXL -&gt;
XRXLRXRXL -&gt;
XRLXRXRXL -&gt;
XRLXXRRXL -&gt;
XRLXXRRLX
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> start = &quot;X&quot;, end = &quot;L&quot;
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= start.length&nbsp;&lt;= 10<sup>4</sup></code></li>
	<li><code>start.length == end.length</code></li>
	<li>Both <code>start</code> and <code>end</code> will only consist of characters in <code>&#39;L&#39;</code>, <code>&#39;R&#39;</code>, and&nbsp;<code>&#39;X&#39;</code>.</li>
</ul>

class Solution {
public:
    bool canTransform(string start, string end) {
        int sz = end.size(), cntl = 0, cntr = 0;
        vector<int> ls(sz,0), rs(sz,0);
        deque<int> lx,rx;

        for(int i=0; i < sz; i++){
            bool cond1 = start[i] == 'L' && end[i] == 'R';
            bool cond2 = start[i] == 'R' && end[i] == 'L';
            bool cond3 = start[i] == 'L' && end[i] == 'X';
            bool cond4 = start[i] == 'R' && end[i] == 'X';

            if(cond1 || cond2)
                return false;
            else if(cond3)
                lx.push_back(i);
            else if(cond4)
                rx.push_back(i);
            
            ls[i] = (!i ? 0 : ls[i-1]) + (start[i] == 'L');
            rs[i] = (!i ? 0 : rs[i-1]) + (start[i] == 'R');
            cntl += (end[i] == 'L');
            cntr += (end[i] == 'R');
        }

        if(ls[sz-1] != cntl || rs[sz-1] != cntr)
            return false;

        for(int i=0;i<sz;i++){
            bool cond1 = start[i] == 'X' && end[i] == 'R';
            bool cond2 = start[i] == 'X' && end[i] == 'L';

            if(cond1) {
                int pos = rx.front();
                int Lcnt = ls[i] - ls[pos];
                if(pos >= i || Lcnt)
                    return false;
                rx.pop_front();
            } else if(cond2) {
                int pos = lx.front();
                int Rcnt = rs[pos] - rs[i];
                if(pos <= i || Rcnt)
                    return false;
                lx.pop_front();
            }
        }

        return true;
    }
};
10500