Move Pieces to Obtain a String
Problem 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.
Examples
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.
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.
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 '_'.
It looks likes, we can easily give the solution but doubting how to implement right! We think there is something... this can be possibly solved using some conditions mentioned in the problem. Ok, let's figure out what it would be through some analysis.
Optimal Approach
Intuition
Okay, now we will have a look on the given conditions from the problem description and analyze those conditions.
Let’s Consider the example, start = “_ L _ _” , target = “_ _ _ L”For now assume that we don’t have the “R” in our way. After observing the above example we can simply say that we can’t do moves in such a way to start turns as the target! Why……. as per the conditions mentioned in the question, ‘L’ in the start can only move to the Left. So, at any cost we can't move ‘L’ to the Right side right! so we return false .
Fine, then let's have this now - start = “_ _ _ L” , target = “_ L _ _” . In this example we can move the L to the Left.
Now we will take another sample, start = “_ L _ _ ” , target = “_ L _ _” , we need not to move ‘L’ in start to make it as target, as the position of “L” in both are same.
So,what can we conclude from the above examples? The index of ‘L’ in the target is >= to the index of ‘L’ in start. Isn’t it ?
Now let’s have another example by keeping ‘L’ aside. Consider the example, start = “_ _ R _” , target = “R _ _ _ ” .
From the above example what can we say ? Here also , it is not possible to move “R” in the start to the left to turn the start as target right? Why? As per the conditions mentioned in the problem ‘R’ can only move to the right side only. So, we return False Let’s take one more example - start = “R _ _ _ ” , target = “_ _ R _”
OOps ! We need to return True because, R can move step by step to the right side and can reach the 2nd index in start right whenever the R is at 2nd position, the start and the target are the same na. So we return True.
What if the position of ‘R’ in both start and target are the same without making any move? Absolutely we return true because start and target are already the same right!So, from the above what can we say ? Index of ‘R’ in start should be <= to the index of ‘R’ in target , this is what we observed there!
Okay, fine.. Everything is looking good, but here is the one case that satisfies above both cases, but returns false. What would you say ? Alright, let’s have a different case now. Consider this example, start = “_ R L _” , target = “_ L R _” .
As per the previous conditions - Index of ‘R’ in start < = Index of ‘R’ in target and Index of ‘L’ in start > = Index of ‘L’ in target, though these conditions are well satisfied , the expected output is False. Why? If we observe the conditions given in the problem, they cannot pass through each other. So,In-order to achieve the target, Ls and Rs has to pass each other, but it's not possible, so we return False. That’s good, what can we conclude from the above example? After skipping underscores (_) we will reach the particular character in both Start and Target , if those characters are not the same we will return False.
So, from the above we can say? The order of Ls and Rs should be the same in start and target. This is the 3rd condition that should be satisfied inorder to make the start as target.
If we observe that first "L" in start can be moved and first "R" in target can be moved. But, we can't take the extra one in the start in-order to make it as target right
Let’s see one example that follows the 3 conditions-
Start = “_ _ R _ _ L _ _ L”
Target = “_ _ _ R L _ _ L _”
Ignoring the “_”s the order in start is “RLL” and the order in target is “RLL” . And also every element except ‘_’ is following their corresponding rules . So, we change the start to target and return True.
There is one more case we have to look.
start = "_ L R _ _ L"
target = "L _ _ R _ _ _"
As we discussed about skipping the '_'s, we can have this example where we need to return false.
At first, after skipping all the starting ' _ 's , we reach 'L' in both strings and those are also satisfies the index conditions and agian after skipping the ' _ 's , we reach the 'R' in both strings and those are also satisfies the index conditions.
Finally, after skipping the underscores we reach 'L' in 'start' and there is nothing left in the target to be checked that means there is some extra characters('L','R') are there in any one of them(in this example extra character left in start ), which is/are impossible to remove as we are only allowed move those.
But, how can we say that one might have extra characters? Simple, while iterating through strings if we haven't reach the end of the both strings simultaneously then there are some extra characters left in any one of strings otherwise we return True as we iterated full.
To efficiently validate the transformation of start to target,focus on comparing the strings using two pointers (start_pointer and target_pointer). start_pointer starts from 0 and traverses on Start and target_pointer starts from 0 and traverses on Target, these pointers allow us to traverse both strings simultaneously, skipping underscores (_) since they don't affect the transformation rules. Here Two-pointers concepts work effectively to the problem.
Approach
Step 1:Use start_pointer and target_pointer to traverse the start and target strings.
We will continue the below process until either of the pointers reach the end of the corresponding strings using a while loop.
Step 2: Skip all '_' characters in both strings, focusing on 'L' and 'R' using a while loop.
Step 3: If both pointers have reached the end of their respective strings (i.e., no more characters to compare), return true.
Step 4: If one string is exhausted while the other still has characters left, return false.
Step 5:If characters at start[start_pointer] and target[target_pointer] don’t match, return false.(Not in same order)
Step 6: For 'L': Ensure it doesn’t move right (i.e., start_pointer should not be less than target_pointer).
For 'R': Ensure it doesn’t move left (i.e., start_pointer should not be greater than target_pointer).
Step 7: After one pointer finishes, ensure the other string only contains blanks (_). If not, return false.
Step 8: If while loop completed without returning anything, that tells us our start can be changed to target. So, we return True.
Dry Run
Input:
Start = “_ L _ L _ R _ _ _ L _” Target = “_ L L _ _ _ R _ _ _ L”
Output : False
Explanation : The last ‘L’ at the index 9 in start can’t be moved to index 10 to make both strings equal. So, we return False
Initialization:
- Pointers: start_pointer= 0, target_pointer = 0
While loop runs until start_pointer<len(start) and jtarget_pointer<len(target)
First Iteration:
Skip blanks in s and t:
- In start: start_pointer = 1 (points to 'L').
- In target: target_pointer = 1 (points to 'L').
Compare:
- s[start_pointer] = 'L' and t[target_pointer] = 'L'.
- Characters matched and start_pointer>=target_pointer
- So we don’t return False now
Increment both start_pointer,target_pointer. Then
start_pointer=2
target_pointer=2
Second Iteration:
Skip blanks in s and t:
In start: start_pointer = 3 (points to 'L').
In target: target_pointer = 2 (points to 'L').
Compare:
- s[start_pointer] = 'L' and t[target_pointer] = 'L'.
- Characters matched and start_pointer>=target_pointer
- So we don’t return False now
Increment both start_pointer,target_pointer. Then
start_pointer=4
target_pointer=3
Third Iteration:
Skip blanks in s and t:
- In start: start_pointer = 5 (points to 'R').
- In target: target_pointer = 6 (points to 'R').
Compare:
- s[start_pointer] = 'R' and t[target_pointer] = 'R'.
- Characters matched and start_pointer<=target_pointer
- So we don’t return False now
Increment both start_pointer,target_pointer. Then
start_pointer=6
target_pointer=7
Fourth Iteration:
Skip blanks in s and t:
- In start: start_pointer = 9 (points to 'L').
- In target: target_pointer = 10 (points to 'L').
Compare:
- s[start_pointer] = 'L' and t[target_pointer] = 'L'.
- Characters matched.
- But, start_pointer<target_pointer which contradicts to our rules , if return False as we know the “L” cannot be moved to right
Result:
The transformation is not possible, so the output is: False. (Because in-order to make the start as target , L has to be moved to the right side , but it’s not possible)
Optimal Code in all Languages
1. C++ Try on Compiler
class Solution {
public:
bool canChange(string start, string target) {
// Length of the strings
int n = start.length();
// Initialize pointers for both strings
int start_pointer = 0, target_pointer = 0;
// Traverse both strings
while (start_pointer < n || target_pointer < n) {
// Skip blank spaces in 'start'
while (start_pointer < n && start[start_pointer] == '_') {
start_pointer++;
}
// Skip blank spaces in 'target'
while (target_pointer < n && target[target_pointer] == '_') {
target_pointer++;
}
// If both pointers exceed the length, we are done
if (start_pointer == n && target_pointer == n) return true;
// If one string is exhausted while the other isn't, return false
if (start_pointer == n || target_pointer == n) return false;
// Compare characters at the current position
if (start[start_pointer] != target[target_pointer]) {
return false;
}
// Check if 'L' can only move left
if (start[start_pointer] == 'L' && start_pointer < target_pointer) {
return false;
}
// Check if 'R' can only move right
if (start[start_pointer] == 'R' && start_pointer > target_pointer) {
return false;
}
// Move both pointers forward
start_pointer++;
target_pointer++;
}
// If all checks are passed, return true
return true;
}
};2. Java Try on Compiler
class Solution {
public boolean canChange(String start, String target) {
// Length of the strings
int n = start.length();
// Initialize pointers for both strings
int start_pointer = 0, target_pointer = 0;
// Traverse both strings
while (start_pointer < n || target_pointer < n) {
// Skip blank spaces in 'start'
while (start_pointer < n && start.charAt(start_pointer) == '_') {
start_pointer++;
}
// Skip blank spaces in 'target'
while (target_pointer < n && target.charAt(target_pointer) == '_') {
target_pointer++;
}
// If both pointers exceed the length, we are done
if (start_pointer == n && target_pointer == n) return true;
// If one string is exhausted while the other isn't, return false
if (start_pointer == n || target_pointer == n) return false;
// Compare characters at the current position
if (start.charAt(start_pointer) != target.charAt(target_pointer)) {
return false;
}
// Check if 'L' can only move left
if (start.charAt(start_pointer) == 'L' && start_pointer < target_pointer) {
return false;
}
// Check if 'R' can only move right
if (start.charAt(start_pointer) == 'R' && start_pointer > target_pointer) {
return false;
}
// Move both pointers forward
start_pointer++;
target_pointer++;
}
// If all checks are passed, return true
return true;
}
}3. Python Try on Compiler
class Solution:
def canChange(self, start: str, target: str) -> bool:
# Length of the strings
n = len(start)
# Initialize pointers for both strings
start_pointer, target_pointer = 0, 0
# Traverse both strings
while start_pointer < n or target_pointer < n:
# Skip blank spaces in 'start'
while start_pointer < n and start[start_pointer] == '_':
start_pointer += 1
# Skip blank spaces in 'target'
while target_pointer < n and target[target_pointer] == '_':
target_pointer += 1
# If both pointers exceed the length, we are done
if start_pointer == n and target_pointer == n:
return True
# If one string is exhausted while the other isn't, return false
if start_pointer == n or target_pointer == n:
return False
# Compare characters at the current position
if start[start_pointer] != target[target_pointer]:
return False
# Check if 'L' can only move left
if start[start_pointer] == 'L' and start_pointer < target_pointer:
return False
# Check if 'R' can only move right
if start[start_pointer] == 'R' and start_pointer > target_pointer:
return False
# Move both pointers forward
start_pointer += 1
target_pointer += 1
# If all checks are passed, return True
return True4. JavaScript Try on Compiler
var canChange = function(start, target) {
let n = start.length;
let start_pointer = 0, target_pointer = 0;
// Traverse both strings
while (start_pointer < n || target_pointer < n) {
// Skip underscores in both strings
while (start_pointer < n && start[start_pointer] === '_') start_pointer++;
while (target_pointer < n && target[target_pointer] === '_') target_pointer++;
// If both pointers exceed the length, we are done
if (start_pointer >= n && target_pointer >= n) return true;
// If one string is exhausted while the other isn't, return false
if (start_pointer >= n || target_pointer >= n) return false;
// If characters at the current positions don't match, return false
if (start[start_pointer] !== target[target_pointer]) return false;
// Check if 'L' is moving right or 'R' is moving left (invalid moves)
if (start[start_pointer] === 'L' && start_pointer < target_pointer) return false;
if (start[start_pointer] === 'R' && start_pointer > target_pointer) return false;
// Move pointers forward
start_pointer++;
target_pointer++;
}
return true;
};Time Complexity : O(n)
Length Calculation and Initialization:Calculating the length of the input and initializing pointers both require a single traversal of the data, which takes O(n) time, where n is the size of the input.
Pointer Traversal:The loop iterates through the data at most n times. Each operation inside the loop, such as moving a pointer or performing a simple comparison, takes O(1) time. Therefore, this part also contributes O(n) to the time complexity.
Total Time Complexity:Adding up these steps, we get
O(n)+O(n)=O(2n)≈ O(n) .
Space Complexity : O(n)
Auxiliary space Complexity: It refers to the extra space used by an algorithm during its execution, excluding the input data
- Our implementation only uses a few pointers for traversal and logic, such as start_pointer, target_pointer. These pointers require a constant amount of extra space, which is O(1).
Total Space Complexity
For inputs of start and target - O(n) + O(n) = O(2n) ≈ O(n)
For auxiliary space - O(1)
Total - O(n) + O(1) ≈ O(n)
Learning Tip
You are given two strings sentence1 and sentence2, each representing a sentence composed of words.
A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of only uppercase and lowercase English characters.
Two sentences s1 and s2 are considered similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal.
Note that the inserted sentence must be separated from existing words by spaces.
For example, s1 = "Hello Jane" and s2 = "Hello my name is Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in s1.
s1 = "Frog cool" and s2 = "Frogs are cool" are not similar, since although there is a sentence "s are" inserted into s1, it is not separated from "Frog" by a space.
Given two sentences sentence1 and sentence2, return true if sentence1 and sentence2 are similar. Otherwise, return false.
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.