leetcode - 2337. Move Pieces to Obtain a String

Description

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 <= 10^5
start and target consist of the characters 'L', 'R', and '_'.

Solution

$o(n)$ space

Solved after help…

The result is true when:

1. Without _, start and target should be the same
2. All Ls in start should be at the right of Ls in target
3. All Rs in start should be at the left of Rs in target

So we could use a list to store the L and R in both string and compare the indexes.

Time complexity: $o(n)$
Space complexity: $o(n)$

Optimized Space

Use 2 pointers, when we see _, skipping. All start’s L should be at the right of target’s L, and start’s R should be at the left of target’s R.

Time complexity: $o(n)$
Space complexity: $o(1)$

Code

$o(n)$ space

class Solution:def canChange(self, start: str, target: str) -> bool:start_ls, start_rs = [], []target_ls, target_rs = [], []for i in range(len(start)):if start[i] == 'L':start_ls.append(i)elif start[i] == 'R':start_rs.append(i)if target[i] == 'L':target_ls.append(i)elif target[i] == 'R':target_rs.append(i)if len(start_ls) != len(target_ls) or len(start_rs) != len(target_rs):return Falsefor i in range(len(start_ls)):if start_ls[i] < target_ls[i]:return Falsefor i in range(len(start_rs)):if start_rs[i] > target_rs[i]:return Falsereturn True and start.replace('_', '') == target.replace('_', '')

Optimized Space

class Solution:def canChange(self, start: str, target: str) -> bool:p1, p2 = 0, 0while p1 < len(start) or p2 < len(target):while p1 < len(start) and start[p1] == '_':p1 += 1while p2 < len(target) and target[p2] == '_':p2 += 1if p1 == len(start) or p2 == len(target):return p1 == p2 == len(start)if start[p1] != target[p2]:return Falseif start[p1] == 'L' and p1 < p2:return Falseif start[p1] == 'R' and p1 > p2:return Falsep1 += 1p2 += 1return True