Swapping adjacents in LR string ~ Programming Ninja

We are given a string that is composed of characters "X", "L", "R", like "XXLRXLRXXX", where L represents left and R represents right. A character R can only move to the right and character L can only move to left.

A move consists of either replacing "XL" with "LX" or "RX" with "XR". We are given an original string and a resultant string. Return true if there exits a sequence of moves for converting one string to another.
Example:
Input: original: "XLRRXXRXX", resultant: "LXXXXXRRR"
Output: True

Solution:

First, we check if both the strings are of equal length. If not return false. Now for both the strings, we can convert them to strings with omitting the character "X" since character ''L" and "R" can never cross one another so the generated by omitting "X" should be same.

But along with this, there will be cases like this: "XXLXX" to "XXXLX". Now the strings generated from both these strings after omitting "X" will be the same but this is not possible as "L" can only move to left, so along with characters "L" and "R" we store the indices of these characters as well.

Now the index of "R" in the original string should always be less than in the resultant string, since "R" can only move to the right. Similarly, for "L" it should always be greater than the index in the resultant string.

Code:

bool canTransform(string original, string resultant) {

if(original.length()!=resultant.length())

return false;

vector<pair<char,int>> a,b;

for(int i=0;i<original.length();i++)

{

if(original[i]=='L'||original[i]=='R')

a.push_back({original[i],i});

if(resulttant[i]=='L'||resultant[i]=='R')

b.push_back({resulttant[i],i});

}

if(a.size()!=b.size())

return false;

for(int i=0;i<a.size();i++)

{

if(a[i].first!=b[i].first)

return false;

if(a[i].first=='R'&&a[i].second>b[i].second)

return false;

if(a[i].first=='L'&&a[i].second<b[i].second)

return false;

}

return true;

}

Do share the post if you find it helpful and comment if you have some new insights about the problem.

Happy Programming

About Home

Programming ninja