Leetcode 2337: Move Pieces to Obtain a String
You are given two strings
start and target, each consisting of the characters 'L', 'R', and '_'. The goal is to check if it is possible to transform the string start into target by moving the ‘L’ and ‘R’ characters. ‘L’ can only move to the left and ‘R’ can only move to the right. A blank space can be occupied by either ‘L’ or ‘R’.Problem
Approach
Steps
Complexity
Input: The input consists of two strings, `start` and `target`, each of length `n`.
Example: start = '_L__R__R_', target = 'L______RR'
Constraints:
• 1 <= n <= 10^5
• start and target consist of the characters 'L', 'R', and '_'.
Output: Return `true` if it is possible to obtain the target string from the start string, otherwise return `false`.
Example: true
Constraints:
Goal: Determine if it is possible to transform `start` into `target` by moving pieces according to the described rules.
Steps:
• Initialize two queues to store the positions of the 'L' and 'R' pieces in `start` and `target`.
• Compare the characters in both queues to ensure they match.
• Ensure that the 'L' pieces in `start` do not move right in `target` and the 'R' pieces do not move left.
Goal: The strings are of equal length and consist only of 'L', 'R', and '_'. The length `n` can be up to 100,000.
Steps:
• 1 <= n <= 10^5
• start and target consist of the characters 'L', 'R', and '_'.
Assumptions:
• The input strings are valid and consist only of 'L', 'R', and '_'.
• The strings are of equal length.
• Input: start = '_L__R__R_', target = 'L______RR'
• Explanation: The goal is to check if it's possible to transform the start string into the target string by moving 'L' and 'R' pieces according to the rules. This is possible, as described in the explanation.
Approach: The approach involves comparing the positions of the 'L' and 'R' characters in both strings and ensuring that no piece violates the movement restrictions.
Observations:
• The pieces can only move left or right, but the movement is restricted by their position relative to each other.
• We need to simulate the movements of the pieces and check if the positions match between the two strings under the given constraints.
Steps:
• Initialize two queues to track the 'L' and 'R' positions.
• Compare the queues to check if each piece in `start` can be transformed into the corresponding piece in `target` while respecting movement restrictions.
Empty Inputs:
• Empty strings are not valid as per the constraints.
Large Inputs:
• Ensure that the solution handles input sizes up to 100,000 characters efficiently.
Special Values:
• If all characters are '_', the target string should be exactly the same as the start string.
Constraints:
• The strings should always have a length of at least 1 and no more than 100,000 characters.
bool canChange(string start, string target) {
queue<pair<int, int>> ss, ts;
for(int i = 0; i < start.size(); i++)
if(start[i] != '_') ss.push({start[i], i});
for(int i = 0; i < target.size(); i++)
if(target[i] != '_') ts.push({target[i], i});
if(ss.size() != ts.size()) return false;
while(!ss.empty()) {
auto s = ss.front();
auto t = ts.front();
ss.pop();
ts.pop();
if(s.first != t.first) return false;
if(s.first == 'L' && t.second > s.second)
return false;
if(t.first == 'R' && t.second < s.second)
return false;
}
return true;
}
1 : Code Block
bool canChange(string start, string target) {
Define the function 'canChange' that takes two strings, 'start' and 'target', representing the initial and target states respectively.
2 : Variable Initialization
queue<pair<int, int>> ss, ts;
Declare two queues, 'ss' and 'ts', to store the characters and their indices for the 'start' and 'target' strings.
3 : Loop
for(int i = 0; i < start.size(); i++)
Loop through the characters of the 'start' string.
4 : Push Non-Underscore Characters
if(start[i] != '_') ss.push({start[i], i});
Push each character from 'start' and its index into the queue 'ss', if the character is not an underscore.
5 : Loop
for(int i = 0; i < target.size(); i++)
Loop through the characters of the 'target' string.
6 : Push Non-Underscore Characters
if(target[i] != '_') ts.push({target[i], i});
Push each character from 'target' and its index into the queue 'ts', if the character is not an underscore.
7 : Check Queue Sizes
if(ss.size() != ts.size()) return false;
Check if the sizes of the two queues are the same; if not, return false because the number of non-underscore characters doesn't match.
8 : Begin While Loop
while(!ss.empty()) {
Start a while loop to process the elements in the queues.
9 : Pop from Queues
auto s = ss.front();
Pop the front element from queue 'ss'.
10 : Pop from Queues
auto t = ts.front();
Pop the front element from queue 'ts'.
11 : Remove from Queues
ss.pop();
Remove the front element from queue 'ss'.
12 : Remove from Queues
ts.pop();
Remove the front element from queue 'ts'.
13 : Check Character Equality
if(s.first != t.first) return false;
Check if the characters from both queues are equal; if not, return false.
14 : Character Movement Conditions
if(s.first == 'L' && t.second > s.second)
Check if a 'L' character in the 'start' string violates the movement condition, meaning it should not move to the right.
15 : Return False
return false;
Return false if the movement condition is violated for 'L' characters.
16 : Character Movement Conditions
if(t.first == 'R' && t.second < s.second)
Check if a 'R' character in the 'target' string violates the movement condition, meaning it should not move to the left.
17 : Return False
return false;
Return false if the movement condition is violated for 'R' characters.
18 : Return True
return true;
Return true if all conditions are met, indicating the transformation is possible.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we traverse each string once and perform constant-time operations for each character.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the space used by the queues storing the positions of the 'L' and 'R' pieces.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus