2337. Move Pieces to Obtain a String - Solution

Q: Is Move Pieces to Obtain a String easy or hard?

Move Pieces to Obtain a String is rated Medium difficulty. The challenge lies in recognizing that piece order never changes and translating movement rules into index comparisons during a single pass through the strings.

Q: Move Pieces to Obtain a String Python/Java solution

Python and Java implementations follow the same logic: iterate with two indices across both strings, skip underscores, compare characters, and validate movement constraints for L and R. The algorithm runs in O(n) time and constant extra space in both languages.

Q: How to solve Move Pieces to Obtain a String in O(n)?

Scan both strings with two pointers while skipping underscore characters. When the next non-blank characters match, check their indices: L must not move to the right and R must not move to the left. Continue advancing pointers until the end of both strings. This linear scan validates the transformation in O(n) time.

Q: What is the best approach for Move Pieces to Obtain a String?

The most efficient approach uses two pointers to compare positions of non-blank characters in the start and target strings. First ensure the order of L and R characters is identical after removing underscores. Then enforce movement constraints: L cannot move right and R cannot move left. This solution runs in O(n) time and O(1) space.

Q: Is Move Pieces to Obtain a String asked at Google/Amazon/Meta?

String transformation and constraint-validation problems like this commonly appear in interviews at companies such as Amazon, Google, and Meta. The question tests reasoning about movement constraints and efficient string scanning using two pointers.

Q: What data structure is used in Move Pieces to Obtain a String?

The solution mainly relies on string traversal with the two-pointer technique. No complex data structures are required because the problem reduces to comparing character order and validating positional constraints.

Q: What is the time complexity of Move Pieces to Obtain a String?

The optimal solution runs in O(n) time because each string is scanned once with two pointers. Space complexity is O(1) since only index variables are used and no additional data structures are required.

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

Approach overview

Problem Overview: You are given two strings start and target containing characters L, R, and _ (blank). Pieces can move only in specific directions: L moves left and R moves right by swapping with blanks. The task is to determine whether the start configuration can transform into target under these movement constraints.

Approach 1: Simulate Piece Movement (O(n) time, O(1) space)

This method walks through both strings and simulates how pieces could move through blanks. You skip underscore characters and align the next non-blank characters in both strings. If the characters differ, the transformation is impossible. When they match, enforce movement rules: an L piece cannot appear to the right of its original index because it can only move left, and an R piece cannot appear to the left of its original index because it can only move right. This approach effectively models valid moves while scanning once, making it efficient for large inputs.

Approach 2: Check Character Positions after Removing Blanks (O(n) time, O(1) space)

The key insight is that blanks do not affect the relative ordering of pieces. First remove all underscores from both strings and verify that the remaining sequence of L and R characters is identical. If the order differs, the transformation cannot happen. Next iterate through the original strings using two pointers to compare positions of corresponding pieces. Enforce the constraints: L must not move right and R must not move left. Because each pointer only moves forward once, the scan runs in linear time.

Both strategies rely on the same structural insight: the order of non-blank characters never changes. The problem becomes a positional constraint check rather than actual simulation of swaps. This turns what looks like a movement puzzle into a simple linear scan over a string.

Recommended for interviews: The position-check method using two pointers is the expected solution. It clearly demonstrates understanding of the movement constraints and achieves O(n) time with O(1) extra space. Simulation works too, but recognizing that only relative order and directional constraints matter shows stronger problem-solving insight.

Approach 1: Check Character Positions after Removing Blanks

In this approach, both start and target strings are reduced by removing the blank spaces ('_'). After that, we directly compare the remaining sequences of characters to check if they match. Each character's position is then validated based on the rules: 'L' can only move left, and 'R' can only move right. If these sequences not only match but also adhere to the movement rules, the transformation is possible.

Python

def canChange(start: str, target: str) -> bool:
    if start.replace('_', '') != target.replace('_', ''):
        return False
    
    start_L_positions = [i for i, c in enumerate(start) if c == 'L']
    target_L_positions = [i for i, c in enumerate(target) if c == 'L']
    for s_pos, t_pos in zip(start_L_positions, target_L_positions):
        if s_pos < t_pos:
            return False

    start_R_positions = [i for i, c in enumerate(start) if c == 'R']
    target_R_positions = [i for i, c in enumerate(target) if c == 'R']
    for s_pos, t_pos in zip(start_R_positions, target_R_positions):
        if s_pos > t_pos:
            return False
    
    return True

Java

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

        ArrayList<Integer> startLPositions = new ArrayList<>();
        ArrayList<Integer> targetLPositions = new ArrayList<>();
        for (int i = 0; i < start.length(); i++) {
            if (start.charAt(i) == 'L') startLPositions.add(i);
            if (target.charAt(i) == 'L') targetLPositions.add(i);
        }
        for (int i = 0; i < startLPositions.size(); i++) {
            if (startLPositions.get(i) < targetLPositions.get(i)) return false;
        }

        ArrayList<Integer> startRPositions = new ArrayList<>();
        ArrayList<Integer> targetRPositions = new ArrayList<>();
        for (int i = 0; i < start.length(); i++) {
            if (start.charAt(i) == 'R') startRPositions.add(i);
            if (target.charAt(i) == 'R') targetRPositions.add(i);
        }
        for (int i = 0; i < startRPositions.size(); i++) {
            if (startRPositions.get(i) > targetRPositions.get(i)) return false;
        }

        return true;
    }
}

C++

#include <string>
#include <vector>

using namespace std;

bool canChange(string start, string target) {
    string filteredStart, filteredTarget;
    vector<int> startLPos, targetLPos;
    vector<int> startRPos, targetRPos;
    
    for(int i = 0; i < start.size(); i++) {
        if(start[i] == 'L') startLPos.push_back(i);
        if(target[i] == 'L') targetLPos.push_back(i);
        if(start[i] != '_') filteredStart += start[i];
        if(target[i] != '_') filteredTarget += target[i];
    }

    if (filteredStart != filteredTarget) return false;

    for(int i = 0; i < startLPos.size(); i++) {
        if(startLPos[i] < targetLPos[i]) return false;
    }
    
    for(int i = 0; i < start.size(); i++) {
        if(start[i] == 'R') startRPos.push_back(i);
        if(target[i] == 'R') targetRPos.push_back(i);
    }

    for(int i = 0; i < startRPos.size(); i++) {
        if(startRPos[i] > targetRPos[i]) return false;
    }

    return true;
}

JavaScript

function canChange(start, target) {
    if (start.replace(/_/g, '') !== target.replace(/_/g, '')) {
        return false;
    }
    
    let startLPositions = [];
    let targetLPositions = [];
    for (let i = 0; i < start.length; i++) {
        if (start[i] === 'L') startLPositions.push(i);
        if (target[i] === 'L') targetLPositions.push(i);
    }
    for (let i = 0; i < startLPositions.length; i++) {
        if (startLPositions[i] < targetLPositions[i]) return false;
    }

    let startRPositions = [];
    let targetRPositions = [];
    for (let i = 0; i < start.length; i++) {
        if (start[i] === 'R') startRPositions.push(i);
        if (target[i] === 'R') targetRPositions.push(i);
    }
    for (let i = 0; i < startRPositions.length; i++) {
        if (startRPositions[i] > targetRPositions[i]) return false;
    }

    return true;
}

#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

int compareStringsIgnoringBlanks(char *start, char *target) {
    char filteredStart[strlen(start) + 1], filteredTarget[strlen(target) + 1];
    int sIndex = 0, tIndex = 0;
    for (int i = 0; start[i]; i++) {
        if (start[i] != '_') {
            filteredStart[sIndex++] = start[i];
        }
    }
    filteredStart[sIndex] = '\0';
    for (int i = 0; target[i]; i++) {
        if (target[i] != '_') {
            filteredTarget[tIndex++] = target[i];
        }
    }
    filteredTarget[tIndex] = '\0';
    return strcmp(filteredStart, filteredTarget);
}

bool findPositions(char *str, char ch, int *positions, int length) {
    int posCount = 0;
    for (int i = 0; i < length; i++) {
        if (str[i] == ch) {
            positions[posCount++] = i;
        }
    }
    return posCount;
}

bool canChange(char *start, char *target) {
    int n = strlen(start);
    if (compareStringsIgnoringBlanks(start, target) != 0) {
        return false;
    }
    
    int startLP[n], targetLP[n], startRP[n], targetRP[n];
    int startLCount = findPositions(start, 'L', startLP, n);
    int targetLCount = findPositions(target, 'L', targetLP, n);
    int startRCount = findPositions(start, 'R', startRP, n);
    int targetRCount = findPositions(target, 'R', targetRP, n);

    for (int i = 0; i < startLCount; i++) {
        if (startLP[i] < targetLP[i]) {
            return false;
        }
    }

    for (int i = 0; i < startRCount; i++) {
        if (startRP[i] > targetRP[i]) {
            return false;
        }
    }

    return true;
}

using System;
using System.Collections.Generic;

public class Solution {
    public bool CanChange(string start, string target) {
        if(start.Replace("_", "") != target.Replace("_", "")) {
            return false;
        }

        List<int> startLPositions = new List<int>();
        List<int> targetLPositions = new List<int>();
        for(int i = 0; i < start.Length; i++) {
            if(start[i] == 'L') startLPositions.Add(i);
            if(target[i] == 'L') targetLPositions.Add(i);
        }

        for(int i = 0; i < startLPositions.Count; i++) {
            if(startLPositions[i] < targetLPositions[i]) return false;
        }

        List<int> startRPositions = new List<int>();
        List<int> targetRPositions = new List<int>();
        for(int i = 0; i < start.Length; i++) {
            if(start[i] == 'R') startRPositions.Add(i);
            if(target[i] == 'R') targetRPositions.Add(i);
        }

        for(int i = 0; i < startRPositions.Count; i++) {
            if(startRPositions[i] > targetRPositions[i]) return false;
        }
        return true;
    }
}

This Python solution initially checks if both strings can become the same after removing all blanks. Then, it stores the indices of 'L' and 'R' in both strings and compares their positions to ensure all rules are respected: 'L' cannot move right, 'R' cannot move left. The solution returns True only if all conditions are satisfied.

Complexity

Time Complexity: O(n), where n is the length of the input strings, since we traverse through the list a fixed number of times.
Space Complexity: O(n) due to the extra lists created for positions of 'L' and 'R'.

Try this approach in the editor

Approach 2: Simulate Piece Movement

This approach simulates the movement of 'L' and 'R' pieces while iterating through both strings simultaneously. It maintains cursors for both strings, moving them forward as each piece is appropriately moved according to the rules. 'L' must be moved only left, while 'R' needs space to go right, ensuring no rule violations exist.

Python

def canChange(start: str, target: str) -> bool:
    i = j = 0
    n = len(start)

    while i < n and j < n:
        while i < n and start[i] == '_':
            i += 1
        while j < n and target[j] == '_':
            j += 1
        if i < n and j < n:
            if start[i] != target[j]:
                return False
            if start[i] == 'L' and i < j:
                return False
            if start[i] == 'R' and i > j:
                return False
            i += 1
            j += 1
    
    while i < n and start[i] == '_':
        i += 1
    while j < n and target[j] == '_':
        j += 1
    
    return i == j

Java

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

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

            if (i < n && j < n) {
                if (start.charAt(i) != target.charAt(j)) return false;
                if (start.charAt(i) == 'L' && i < j) return false;
                if (start.charAt(i) == 'R' && i > j) return false;
                i++;
                j++;
            }
        }

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

        return i == j;
    }
}

C++

#include <string>

using namespace std;

bool canChange(string start, string target) {
    int i = 0, j = 0;
    int n = start.size();

    while (i < n && j < n) {
        while (i < n && start[i] == '_') i++;
        while (j < n && target[j] == '_') j++;

        if (i < n && j < n) {
            if (start[i] != target[j]) return false;
            if (start[i] == 'L' && i < j) return false;
            if (start[i] == 'R' && i > j) return false;
            i++;
            j++;
        }
    }

    while (i < n && start[i] == '_') i++;
    while (j < n && target[j] == '_') j++;

    return i == j;
}

JavaScript

function canChange(start, target) {
    let i = 0, j = 0;
    const n = start.length;

    while (i < n && j < n) {
        while (i < n && start[i] === '_') i++;
        while (j < n && target[j] === '_') j++;

        if (i < n && j < n) {
            if (start[i] !== target[j]) return false;
            if (start[i] === 'L' && i < j) return false;
            if (start[i] === 'R' && i > j) return false;
            i++;
            j++;
        }
    }

    while (i < n && start[i] === '_') i++;
    while (j < n && target[j] === '_') j++;

    return i === j;
}

#include <stdbool.h>
#include <string.h>

bool canChange(const char *start, const char *target) {
    int i = 0, j = 0;
    int n = strlen(start);

    while (i < n && j < n) {
        while (i < n && start[i] == '_') i++;
        while (j < n && target[j] == '_') j++;

        if (i < n && j < n) {
            if (start[i] != target[j]) return false;
            if (start[i] == 'L' && i < j) return false;
            if (start[i] == 'R' && i > j) return false;
            i++;
            j++;
        }
    }

    while (i < n && start[i] == '_') i++;
    while (j < n && target[j] == '_') j++;

    return i == j;
}

public class Solution {
    public bool CanChange(string start, string target) {
        int i = 0, j = 0;
        int n = start.Length;

        while (i < n && j < n) {
            while (i < n && start[i] == '_') i++;
            while (j < n && target[j] == '_') j++;

            if (i < n && j < n) {
                if (start[i] != target[j]) return false;
                if (start[i] == 'L' && i < j) return false;
                if (start[i] == 'R' && i > j) return false;
                i++;
                j++;
            }
        }

        while (i < n && start[i] == '_') i++;
        while (j < n && target[j] == '_') j++;

        return i == j;
    }
}

This Python implementation uses two pointers, one for each string, skipping underscores, and comparing positions. It checks the position rules for 'L' and 'R'. The final condition ensures no unmatched characters exist. It’s efficient as it simply processes each character once.

Complexity

Time Complexity: O(n), because of the single pass through start and target strings.
Space Complexity: O(1), as no additional space proportional to the input is utilized.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

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

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
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Check Character Positions after Removing Blanks	Time Complexity: O(n), where n is the length of the input strings, since we traverse through the list a fixed number of times. Space Complexity: O(n) due to the extra lists created for positions of 'L' and 'R'.
Simulate Piece Movement	Time Complexity: O(n), because of the single pass through start and target strings. Space Complexity: O(1), as no additional space proportional to the input is utilized.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Simulate Piece Movement	O(n)	O(1)	Good for understanding the movement rules step by step
Check Character Positions after Removing Blanks	O(n)	O(1)	Preferred interview solution; simplest linear validation using two pointers

Frequently asked questions

Is Move Pieces to Obtain a String easy or hard?

Move Pieces to Obtain a String is rated Medium difficulty. The challenge lies in recognizing that piece order never changes and translating movement rules into index comparisons during a single pass through the strings.

Move Pieces to Obtain a String Python/Java solution

Python and Java implementations follow the same logic: iterate with two indices across both strings, skip underscores, compare characters, and validate movement constraints for L and R. The algorithm runs in O(n) time and constant extra space in both languages.

How to solve Move Pieces to Obtain a String in O(n)?

Scan both strings with two pointers while skipping underscore characters. When the next non-blank characters match, check their indices: L must not move to the right and R must not move to the left. Continue advancing pointers until the end of both strings. This linear scan validates the transformation in O(n) time.

What is the best approach for Move Pieces to Obtain a String?

The most efficient approach uses two pointers to compare positions of non-blank characters in the start and target strings. First ensure the order of L and R characters is identical after removing underscores. Then enforce movement constraints: L cannot move right and R cannot move left. This solution runs in O(n) time and O(1) space.

Is Move Pieces to Obtain a String asked at Google/Amazon/Meta?

String transformation and constraint-validation problems like this commonly appear in interviews at companies such as Amazon, Google, and Meta. The question tests reasoning about movement constraints and efficient string scanning using two pointers.

What data structure is used in Move Pieces to Obtain a String?

The solution mainly relies on string traversal with the two-pointer technique. No complex data structures are required because the problem reduces to comparing character order and validating positional constraints.

What is the time complexity of Move Pieces to Obtain a String?

The optimal solution runs in O(n) time because each string is scanned once with two pointers. Space complexity is O(1) since only index variables are used and no additional data structures are required.

Move Pieces to Obtain a String solution and explanation

The problem

Approach overview

Approach 1: Check Character Positions after Removing Blanks

Approach 2: Simulate Piece Movement

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Move Pieces to Obtain a String solution and explanation

The problem

Approach overview

Approach 1: Check Character Positions after Removing Blanks

Approach 2: Simulate Piece Movement

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems