Move Pieces to Obtain a String

Move Pieces to Obtain a String is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the In-place Array Modification subpattern.

Problem statement

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 = "LRR", target = "LRR" 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 "LRR". - Move the last piece one step to the right, start becomes equal to "LRR". - Move the second piece three steps to the right, start becomes equal to "LRR". Since it is possible to get the string target from start, we return true.

Example 2:

Input: start = "RL", 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 ''.

Topics and companies

Topics: Two Pointers, String.

How to practise Move Pieces to Obtain a String on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n), where n is the length of the strings. Each character is visited at most once by each pointer. time and O(1), as only a constant amount of extra space is used (pointers and counters). space.

Open Move Pieces to Obtain a String in the code editor, or read the Move Pieces to Obtain a String editorial for a worked solution with its approach and complexity analysis.

Where Move Pieces to Obtain a String sits in the DSA pattern sheet

• Two Pointers pattern guide
• In-place Array Modification subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Move Pieces to Obtain a String

Other problems that use the same In-place Array Modification and Two Pointers techniques:

• Intersection of Two Arrays — Easy, same subpattern
• Move Zeroes — Easy, same subpattern
• Remove Duplicates from Sorted Array — Easy, same subpattern
• Remove Duplicates from Sorted Array II — Medium, same subpattern
• Remove Element — Easy, same subpattern
• Separate Black and White Balls — Medium, same subpattern