# Move Pieces to Obtain a String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/move-pieces-to-obtain-a-string)
Canonical: https://scaleengineer.com/dsa/problems/move-pieces-to-obtain-a-string
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
---
## Problem
You are given two strings `start` and `target`, both of length `n`. Each string consists **only** of the characters `'L'`, `'R'`, and `'_'` where:

* The characters `'L'` and `'R'` represent pieces, where a piece `'L'` can move to the **left** only if there is a **blank** space directly to its left, and a piece `'R'` can move to the **right** only if there is a **blank** space directly to its right.
* The character `'_'` represents a blank space that can be occupied by **any** of the `'L'` or `'R'` pieces.

Return `true` _if it is possible to obtain the string_ `target` _by moving the pieces of the string_ `start` _**any** number of times_. Otherwise, return `false`.

**Example 1:**

**Input:** start = "_L__R__R_", target = "L______RR"
**Output:** true
**Explanation:** We can obtain the string target from start by doing the following moves:
- Move the first piece one step to the left, start becomes equal to "**L**___R__R_".
- Move the last piece one step to the right, start becomes equal to "L___R___**R**".
- Move the second piece three steps to the right, start becomes equal to "L______**R**R".
Since it is possible to get the string target from start, we return true.

**Example 2:**

**Input:** start = "R_L_", target = "__LR"
**Output:** false
**Explanation:** The 'R' piece in the string start can move one step to the right to obtain "_**R**L_".
After that, no pieces can move anymore, so it is impossible to obtain the string target from start.

**Example 3:**

**Input:** start = "_R", target = "R_"
**Output:** false
**Explanation:** The piece in the string start can move only to the right, so it is impossible to obtain the string target from start.

**Constraints:**

* `n == start.length == target.length`
* `1 <= n <= 105`
* `start` and `target` consist of the characters `'L'`, `'R'`, and `'_'`.

# Approaches
## Two-Pass Approach with Extra Space
This approach breaks the problem into two main parts. First, it confirms that the relative order of 'L' and 'R' pieces is the same in both `start` and `target` strings. Second, it verifies that each piece's move is valid according to the rules ('L' only moves left, 'R' only moves right). This is done by collecting the indices of all pieces and comparing them.
**Time:** O(N), where N is the length of the strings. Filtering strings, collecting indices, and comparing them each take linear time. · **Space:** O(N), for storing the filtered strings and the lists of indices. In the worst case, where there are no blank spaces, these data structures will be proportional to the input size N.
**Pros:** Conceptually simple and easy to understand.; The logic is broken down into two distinct, verifiable steps.
**Cons:** Uses O(N) extra space, which can be inefficient for very long strings.; Requires multiple passes over the data.
### Explanation
The fundamental insight is that the pieces ('L' and 'R') cannot cross each other. This implies that if we remove all the blank spaces ('_'), the resulting sequence of pieces must be identical for both `start` and `target`. We can check this by creating filtered versions of the strings. For example, `start.replace("_", "").equals(target.replace("_", ""))`. If this condition fails, it's impossible to transform `start` to `target`.

If the piece sequences are the same, we then need to check the movement constraints. An 'L' piece at an initial index `i` can only end up at a final index `j` where `j <= i`. Conversely, an 'R' piece at index `i` can only move to an index `j` where `j >= i`. To verify this for all pieces, we can gather the indices of all 'L's and 'R's from both strings into separate lists. Then, we compare the indices of corresponding pieces. For the k-th 'L' piece, its index in `start` must be greater than or equal to its index in `target`. For the k-th 'R' piece, its index in `start` must be less than or equal to its index in `target`. If any piece violates these rules, the transformation is impossible.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean canChange(String start, String target) {
        if (!start.replace("_", "").equals(target.replace("_", ""))) {
            return false;
        }

        int n = start.length();
        List<Integer> startLIndices = new ArrayList<>();
        List<Integer> startRIndices = new ArrayList<>();
        List<Integer> targetLIndices = new ArrayList<>();
        List<Integer> targetRIndices = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (start.charAt(i) == 'L') {
                startLIndices.add(i);
            } else if (start.charAt(i) == 'R') {
                startRIndices.add(i);
            }
            if (target.charAt(i) == 'L') {
                targetLIndices.add(i);
            } else if (target.charAt(i) == 'R') {
                targetRIndices.add(i);
            }
        }

        for (int i = 0; i < startLIndices.size(); i++) {
            if (startLIndices.get(i) < targetLIndices.get(i)) {
                return false;
            }
        }

        for (int i = 0; i < startRIndices.size(); i++) {
            if (startRIndices.get(i) > targetRIndices.get(i)) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- Create two new strings by removing all `_` characters from `start` and `target`.
- If these new strings are not identical, return `false`.
- Create four lists to store the indices of 'L' and 'R' characters for both `start` and `target` strings.
- Populate these lists by iterating through the original strings.
- Compare the indices for each corresponding 'L' piece. The index in `start` must be greater than or equal to the index in `target`. If not, return `false`.
- Compare the indices for each corresponding 'R' piece. The index in `start` must be less than or equal to the index in `target`. If not, return `false`.
- If all checks pass, return `true`.

## Optimal One-Pass Two-Pointer Approach
This highly efficient approach solves the problem in a single pass using two pointers and constant extra space. The pointers traverse the `start` and `target` strings, skipping blank spaces to find corresponding pieces. At each step, it simultaneously verifies that the piece types match (ensuring relative order is preserved) and that the move is valid based on the piece's position and movement rules.
**Time:** O(N), where N is the length of the strings. Each pointer traverses its respective string exactly once. · **Space:** O(1). The solution uses only a constant amount of extra space for the two pointers, regardless of the input size.
**Pros:** Extremely efficient with O(1) space complexity.; Solves the problem in a single pass over the input strings.
**Cons:** The combined logic within a single loop can be slightly more complex to grasp initially compared to a multi-pass approach.
### Explanation
This optimal solution is built on the same logical foundations as the two-pass approach but achieves constant space complexity by avoiding intermediate data structures. It uses two pointers, `i` for the `start` string and `j` for the `target` string, to find and compare corresponding non-blank characters in one go.

The pointers `i` and `j` are advanced to skip any `_` characters. When both pointers land on a piece, we perform a series of checks:
1.  **Piece Count Mismatch**: If one pointer reaches the end of its string while the other has not, it implies an unequal number of pieces, making the transformation impossible. 
2.  **Relative Order Mismatch**: If `start.charAt(i)` is not equal to `target.charAt(j)`, the relative order of pieces has changed, which is not allowed.
3.  **Movement Rule Violation**: 
    - If the piece is 'L', it must not move right. Therefore, its starting index `i` must be greater than or equal to its target index `j`. An `i < j` condition is invalid.
    - If the piece is 'R', it must not move left. Therefore, its starting index `i` must be less than or equal to its target index `j`. An `i > j` condition is invalid.

If any of these checks fail, we return `false`. Otherwise, we advance both pointers to find the next pair of pieces. If the entire strings are traversed without any violations, it means the transformation is possible, and we return `true`.

```java
class Solution {
    public boolean canChange(String start, String target) {
        int n = start.length();
        int i = 0; // pointer for start
        int j = 0; // pointer for target

        while (i < n || j < n) {
            while (i < n && start.charAt(i) == '_') {
                i++;
            }
            while (j < n && target.charAt(j) == '_') {
                j++;
            }

            if (i == n && j == n) {
                return true;
            }
            if (i == n || j == n) {
                return false;
            }

            if (start.charAt(i) != target.charAt(j)) {
                return false;
            }

            char piece = start.charAt(i);
            if (piece == 'L') {
                if (i < j) {
                    return false;
                }
            } else { // piece == 'R'
                if (i > j) {
                    return false;
                }
            }
            
            i++;
            j++;
        }

        return true;
    }
}
```
### Algorithm
- Initialize two pointers, `i` for `start` and `j` for `target`, both at 0.
- Loop as long as either pointer is within the string bounds (`i < n` or `j < n`).
- Inside the loop, advance `i` and `j` past any `_` characters.
- If both pointers reach the end of the strings, return `true`.
- If only one pointer reaches the end, it means the piece counts differ, so return `false`.
- Check if the pieces at `start[i]` and `target[j]` are different. If so, return `false`.
- Check the movement rules: if it's an 'L' piece and `i < j`, return `false`. If it's an 'R' piece and `i > j`, return `false`.
- Increment both `i` and `j` to process the next pair of pieces.

# Solutions
### Java

```java
class Solution {
public
  boolean canChange(String start, String target) {
    List<int[]> a = f(start);
    List<int[]> b = f(target);
    if (a.size() != b.size()) {
      return false;
    }
    for (int i = 0; i < a.size(); ++i) {
      int[] x = a.get(i);
      int[] y = b.get(i);
      if (x[0] != y[0]) {
        return false;
      }
      if (x[0] == 1 && x[1] < y[1]) {
        return false;
      }
      if (x[0] == 2 && x[1] > y[1]) {
        return false;
      }
    }
    return true;
  }
private
  List<int[]> f(String s) {
    List<int[]> res = new ArrayList<>();
    for (int i = 0; i < s.length(); ++i) {
      if (s.charAt(i) == 'L') {
        res.add(new int[]{1, i});
      } else if (s.charAt(i) == 'R') {
        res.add(new int[]{2, i});
      }
    }
    return res;
  }
}

```

### CPP

```cpp
using pii = pair < int , int > ; class Solution { public: bool canChange ( string start , string target ) { auto a = f ( start ); auto b = f ( target ); if ( a . size () != b . size ()) return false ; for ( int i = 0 ; i < a . size (); ++ i ) { auto x = a [ i ], y = b [ i ]; if ( x . first != y . first ) return false ; if ( x . first == 1 && x . second < y . second ) return false ; if ( x . first == 2 && x . second > y . second ) return false ; } return true ; } vector < pair < int , int >> f ( string s ) { vector < pii > res ; for ( int i = 0 ; i < s . size (); ++ i ) { if ( s [ i ] == 'L' ) res . push_back ({ 1 , i }); else if ( s [ i ] == 'R' ) res . push_back ({ 2 , i }); } return res ; } };
```

### Python

```python
class Solution:
    def canChange(self, start: str, target: str) -> bool: a = [(v, i) for i, v in enumerate(start) if v != '_'] b = [(v, i) for i, v in enumerate(target) if v != '_'] if len(a) != len(b): return False for (c, i), (d, j) in zip(a, b): if c != d: return False if c == 'L' and i < j: return False if c == 'R' and i > j: return False return True

```