Swap Adjacent in LR String

Med

#0731Time: O(N). The `replace` operation takes O(N) time. The subsequent passes to collect and compare indices also take O(N) time. Thus, the total time complexity is linear.Space: O(N), where N is the length of the strings. In the worst case, the strings might contain no 'X's, so the filtered strings and the index lists can take up space proportional to N.

Patterns

Two Pointers

Data structures

String

Prompt

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 result, return True if and only if there exists a sequence of moves to transform start to result.

Example 1:

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

Example 2:

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

Constraints:

1 <= start.length <= 10⁴
start.length == result.length
Both start and result will only consist of characters in 'L', 'R', and 'X'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is based on observing the key properties of the allowed moves. The moves XL -> LX and RX -> XR imply that 'L' characters can only move left past 'X's, and 'R' characters can only move right past 'X's. Crucially, 'L' and 'R' can never move past each other. This leads to two main conditions that must be true for a transformation to be possible:

The sequence of 'L's and 'R's, ignoring 'X's, must be the same in both start and result.
Each 'L' in start must end up at an index less than or equal to its starting index. Each 'R' must end up at an index greater than or equal to its starting index.

This approach verifies these two conditions in two separate passes over the strings.

Algorithm

First, check a fundamental invariant: the relative ordering of 'L' and 'R' characters cannot change. This is because 'L' and 'R' cannot move past each other. We can verify this by removing all 'X's from both start and result strings and checking if the resulting strings are identical. If not, transformation is impossible.
If the first check passes, it means both strings have the same number and sequence of 'L's and 'R's. Now, we must check if the movements are valid.
The move XL -> LX means an 'L' can only move to the left. Therefore, for any k-th 'L' character, its index in the start string must be greater than or equal to its index in the result string.
The move RX -> XR means an 'R' can only move to the right. Therefore, for any k-th 'R' character, its index in the start string must be less than or equal to its index in the result string.
To implement this, we can perform a second pass to collect the indices of all 'L's and 'R's from both strings into separate lists.
Finally, we compare these lists of indices pair-wise to ensure the movement conditions are met.

Walkthrough

The algorithm is implemented in two main steps:

Check Relative Order: We first create two new strings by removing all 'X' characters from start and result. If these two new strings are not equal, it means the relative order of 'L's and 'R's is different, so we can immediately return false. This check efficiently confirms that the counts and sequence of non-'X' characters are the same.
Check Positional Constraints: If the first check passes, we proceed to verify the movement rules. We iterate through the start and result strings to collect the indices of all 'L's and 'R's. We store these indices in four lists: l_start_indices, r_start_indices, l_result_indices, and r_result_indices. Then, we compare the indices for each corresponding character:
- For each i-th 'L', we check if l_start_indices[i] >= l_result_indices[i].
- For each i-th 'R', we check if r_start_indices[i] <= r_result_indices[i]. If any of these conditions are violated, we return false. If all checks pass, the transformation is possible, and we return true.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public boolean canTransform(String start, String result) {6        if (!start.replace("X", "").equals(result.replace("X", ""))) {7            return false;8        }9 10        List<Integer> lStartIndices = new ArrayList<>();11        List<Integer> rStartIndices = new ArrayList<>();12        for (int i = 0; i < start.length(); i++) {13            if (start.charAt(i) == 'L') {14                lStartIndices.add(i);15            } else if (start.charAt(i) == 'R') {16                rStartIndices.add(i);17            }18        }19 20        List<Integer> lResultIndices = new ArrayList<>();21        List<Integer> rResultIndices = new ArrayList<>();22        for (int i = 0; i < result.length(); i++) {23            if (result.charAt(i) == 'L') {24                lResultIndices.add(i);25            } else if (result.charAt(i) == 'R') {26                rResultIndices.add(i);27            }28        }29 30        for (int i = 0; i < lStartIndices.size(); i++) {31            if (lStartIndices.get(i) < lResultIndices.get(i)) {32                return false;33            }34        }35 36        for (int i = 0; i < rStartIndices.size(); i++) {37            if (rStartIndices.get(i) > rResultIndices.get(i)) {38                return false;39            }40        }41 42        return true;43    }44}

Complexity

Time

O(N). The `replace` operation takes O(N) time. The subsequent passes to collect and compare indices also take O(N) time. Thus, the total time complexity is linear.

Space

O(N), where N is the length of the strings. In the worst case, the strings might contain no 'X's, so the filtered strings and the index lists can take up space proportional to N.

Trade-offs

Pros

The logic is straightforward and directly follows from the problem's constraints.
It's relatively easy to implement and debug.

Cons

Requires extra space proportional to the length of the strings to store the filtered strings and the lists of indices.

This approach optimizes the two-pass method by combining all necessary checks into a single pass over the strings. It uses two pointers to simultaneously iterate through the start and result strings, comparing non-'X' characters as they are found. This avoids the need for intermediate data structures like new strings or lists of indices, thus reducing the space complexity to be constant.

Algorithm

Initialize two pointers, i for start and j for result, both starting at 0.
Loop as long as either pointer has not reached the end of its string.
Inside the loop, advance i to the next non-'X' character in start.
Similarly, advance j to the next non-'X' character in result.
After finding the next non-'X' characters, perform checks:
- If one pointer reached the end but the other didn't, the counts of non-'X' characters differ. Return false.
- If both pointers reached the end, all characters have been successfully matched. Return true.
- If start.charAt(i) is not equal to result.charAt(j), the relative order is wrong. Return false.
- If the character is 'L', check if i < j. If so, an 'L' would have had to move right, which is impossible. Return false.
- If the character is 'R', check if i > j. If so, an 'R' would have had to move left, which is impossible. Return false.
If all checks pass for the current pair of characters, increment both i and j to continue the search.

Walkthrough

We can think of the 'X's as empty spaces. The core idea is to match the non-'X' characters of start and result in order and verify their movement rules on the fly.

We use two pointers, i and j, to scan start and result respectively. In each step, we advance both pointers past any 'X's to find the next 'L' or 'R'.

Once we find a non-'X' character in both strings (at start[i] and result[j]), we first check if they are the same character. If not (start[i] != result[j]), it means the relative order of 'L's and 'R's is broken, so we return false.

If the characters match, we check the positional constraints:

If start[i] == 'L', it must have moved left or stayed put. This implies its starting index i must be greater than or equal to its final index j. If i < j, the move is invalid.
If start[i] == 'R', it must have moved right or stayed put. This implies its starting index i must be less than or equal to its final index j. If i > j, the move is invalid.

We repeat this process until we have scanned both strings. If we successfully match all non-'X' characters without violating any rules, the transformation is possible.

1class Solution {2    public boolean canTransform(String start, String result) {3        int n = start.length();4        int i = 0, j = 0;5 6        while (i < n || j < n) {7            while (i < n && start.charAt(i) == 'X') {8                i++;9            }10            while (j < n && result.charAt(j) == 'X') {11                j++;12            }13 14            // If we reached the end of both strings, all non-'X' chars matched.15            if (i == n && j == n) {16                return true;17            }18            19            // If one reached the end but not the other, or chars don't match.20            if (i == n || j == n || start.charAt(i) != result.charAt(j)) {21                return false;22            }23 24            // Check position constraints25            if (start.charAt(i) == 'L') {26                if (i < j) {27                    return false; // 'L' must move left, so start index must be >= result index28                }29            } else { // Character is 'R'30                if (i > j) {31                    return false; // 'R' must move right, so start index must be <= result index32                }33            }34            35            i++;36            j++;37        }38        39        return true;40    }41}

Complexity

Time

O(N), where N is the length of the strings. Each pointer, `i` and `j`, traverses its respective string at most once.

Space

O(1). We only use a few variables to store the pointers, regardless of the input size.

Trade-offs

Pros

Extremely efficient, using only a single pass through the data.
Optimal space complexity, as it uses only O(1) extra space.

Cons

The logic, while efficient, can be slightly more complex to grasp initially compared to the two-pass method due to the combined checks and pointer manipulation.

Solutions

Solution

1class Solution {2public3  boolean canTransform(String start, String end) {4    int n = start.length();5    int i = 0, j = 0;6    while (true) {7      while (i < n && start.charAt(i) == 'X') {8        ++i;9      }10      while (j < n && end.charAt(j) == 'X') {11        ++j;12      }13      if (i == n && j == n) {14        return true;15      }16      if (i == n || j == n || start.charAt(i) != end.charAt(j)) {17        return false;18      }19      if (start.charAt(i) == 'L' && i < j || start.charAt(i) == 'R' && i > j) {20        return false;21      }22      ++i;23      ++j;24    }25  }26}

1class Solution {2public:3  bool canTransform(string start, string end) {4    int n = start.size();5    int i = 0, j = 0;6    while (true) {7      while (i < n && start[i] == 'X')8        ++i;9      while (j < n && end[j] == 'X')10        ++j;11      if (i == n && j == n)12        return true;13      if (i == n || j == n || start[i] != end[j])14        return false;15      if (start[i] == 'L' && i < j)16        return false;17      if (start[i] == 'R' && i > j)18        return false;19      ++i;20      ++j;21    }22  }23};

1class Solution:2    def canTransform(self, start: str, end: str) -> bool: n = len(start) i = j = 0 while 1: while i < n and start[i] == 'X': i += 1 while j < n and end[j] == 'X': j += 1 if i >= n and j >= n: return True if i >= n or j >= n or start[i] != end[j]: return False if start[i] == 'L' and i < j: return False if start[i] == 'R' and i > j: return False i, j = i + 1, j + 1

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem