##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2337.html

# 2337. Move Pieces to Obtain a String

• Difficulty: Medium.
• Related Topics: Two Pointers, String.
• Similar Questions: Valid Parentheses, Swap Adjacent in LR 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______RR".
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 "_RL_".
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 '_'.

## Solution (Java, C++, Python)

• class Solution {
public boolean canChange(String start, String target) {
int i = -1;
int j = -1;
while (true) {
while (true) {
if (++i >= start.length() || start.charAt(i) != '_') {
break;
}
}
while (true) {
if (++j >= target.length() || target.charAt(j) != '_') {
break;
}
}
if (i == start.length() && j == target.length()) {
return true;
}
if (i == start.length() || j == target.length()) {
return false;
}
if ((start.charAt(i) != target.charAt(j)) || (start.charAt(i) == 'L' ? j > i : i > j)) {
return false;
}
}
}
}

############

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;
}
}

• 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

############

# 2337. Move Pieces to Obtain a String
# https://leetcode.com/problems/move-pieces-to-obtain-a-string/

class Solution:
def canChange(self, start: str, target: str) -> bool:
if start == target: return True

s = [(i, x) for i, x in enumerate(start) if x != "_"]
t = [(i, x) for i, x in enumerate(target) if x != "_"]

if len(t) != len(s): return False

for index, (a, b) in enumerate(zip(s, t)):
i, x = a
j, y = b

if x != y: return False

if x == "L":
if i < j: return False
else:
if i > j: return False

return True


• 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;
}
};

• func canChange(start string, target string) bool {
f := func(s string) [][]int {
res := [][]int{}
for i, c := range s {
if c == 'L' {
res = append(res, []int{1, i})
} else if c == 'R' {
res = append(res, []int{2, i})
}
}
return res
}

a, b := f(start), f(target)
if len(a) != len(b) {
return false
}
for i, x := range a {
y := b[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
}

• function canChange(start: string, target: string): boolean {
if (
[...start].filter(c => c !== '_').join('') !==
[...target].filter(c => c !== '_').join('')
) {
return false;
}
const n = start.length;
let i = 0;
let j = 0;
while (i < n || j < n) {
while (start[i] === '_') {
i++;
}
while (target[j] === '_') {
j++;
}
if (start[i] === 'R') {
if (i > j) {
return false;
}
}
if (start[i] === 'L') {
if (i < j) {
return false;
}
}
i++;
j++;
}
return true;
}



Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).