777. Swap Adjacent in LR String
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 1:
Input: start = "RXXLRXRXL"
, end = "XRLXXRRLX"
Output: true
Explanation: We can transform start to end following these steps:
RXXLRXRXL
->
XRXLRXRXL
->
XRLXRXRXL
->
XRLXXRRXL
->
XRLXXRRLX
Example 2:
Input: start = "X", end = "L"
Output: false
Solution
Solution
The first observation we can make is that the two moves can be described as the following: shift L
to the left and shift R
to the right. Since L
and R
cannot be swapped with each other, the relative order of L
and R
letters will never change.
Let's label L
and R
as valid letters.
Our first condition for a transformation from start
to end
is that both start
and end
must have the same number of valid letters. In addition, the first valid letter in start
must match the first valid letter in end
, the second valid letter in start
must match the second valid letter in end
, and so on until the last.
We can also observe that for a transformation to exist, the valid letter in start
must be able to move to the position of the valid letter in end
. We'll denote startIndex
as the index of the valid letter in start
and endIndex
as the index of the valid letter in end
. There are two cases to consider:
- The valid letter is
L
. SinceL
can only move left, a transformation exists whenstartIndex >= endIndex
. - The valid letter is
R
. SinceR
can only move right, a transformation exists whenstartIndex <= endIndex
.
We can implement this using the idea of Two Pointers to keep track of startIndex
and endIndex
for every valid letter.
Time Complexity
Let's denote as the length of both strings start
and end
.
Since we use Two Pointers to iterate through both strings once, our time complexity is .
Time Complexity:
Space Complexity
Space Complexity:
C++ Solution
class Solution {
public:
bool canTransform(string start, string end) {
int n = start.size();
int startIndex = 0;
int endIndex = 0;
while (startIndex < n || endIndex < n) {
while (startIndex < n &&
start[startIndex] == 'X') { // find next valid letter in start
startIndex++;
}
while (endIndex < n &&
end[endIndex] == 'X') { // find next valid letter in end
endIndex++;
}
if (startIndex == n && endIndex == n) { // both reached the end
return true;
}
if (startIndex == n || endIndex == n) { // different number of valid letters
return false;
}
if (start[startIndex] != end[endIndex]) { // different valid letter
return false;
}
if (start[startIndex] == 'R' && startIndex > endIndex) { // wrong direction
return false;
}
if (start[startIndex] == 'L' && startIndex < endIndex) { // wrong direction
return false;
}
startIndex++;
endIndex++;
}
return true;
}
};
Java Solution
class Solution {
public boolean canTransform(String start, String end) {
int n = start.length();
int startIndex = 0;
int endIndex = 0;
while (startIndex < n || endIndex < n) {
while (startIndex < n
&& start.charAt(startIndex) == 'X') { // find next valid letter in start
startIndex++;
}
while (endIndex < n
&& end.charAt(endIndex) == 'X') { // find next valid letter in end
endIndex++;
}
if (startIndex == n && endIndex == n) { // both reached the end
return true;
}
if (startIndex == n || endIndex == n) { // different number of valid letters
return false;
}
if (start.charAt(startIndex)
!= end.charAt(endIndex)) { // different valid letter
return false;
}
if (start.charAt(startIndex) == 'R'
&& startIndex > endIndex) { // wrong direction
return false;
}
if (start.charAt(startIndex) == 'L'
&& startIndex < endIndex) { // wrong direction
return false;
}
startIndex++;
endIndex++;
}
return true;
}
}
Python Solution
class Solution: def canTransform(self, start: str, end: str) -> bool: n = len(start) startIndex = 0 endIndex = 0 while startIndex < n or endIndex < n: while ( startIndex < n and start[startIndex] == "X" ): # find next valid letter in start startIndex += 1 while ( endIndex < n and end[endIndex] == "X" ): # find next valid letter in end endIndex += 1 if startIndex == n and endIndex == n: # both reached the end return True if startIndex == n or endIndex == n: # different number of valid letters return False if start[startIndex] != end[endIndex]: # different valid letter return False if start[startIndex] == "R" and startIndex > endIndex: # wrong direction return False if start[startIndex] == "L" and startIndex < endIndex: # wrong direction return False startIndex += 1 endIndex += 1 return True
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorWhich technique can we use to find the middle of a linked list?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!