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 stringstart any number of times. Otherwise, return false.

Examples

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______**R** R".
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 "_**R** L_".
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 '_'.

Solution

Method 1 - Using two pointer technique

Here is the approach:

  1. Initial Validation:
    • First, ensure that both start and target strings have the exact same sequence of ‘L’ and ‘R’ characters after removing all the ‘_’ characters. If not, transformation is impossible, so return false.
  2. Ignoring Empty Characters:
    • We begin by ignoring all the empty ‘’ characters in both strings. As soon as we encounter any character other than ‘’, the characters in start and target strings must be the same at the current positions.
  3. Movement Constraints:
    • For ‘L’ character:
      • The condition j >= i must hold, if in target string the character is found at index i and in start string it is found at index j.
      • This is because the ‘L’ character can only move to the left in the start string. Hence, if i < j, it means the ‘L’ character cannot move to its corresponding position in target, and we should return false.
    • For ‘R’ character:
      • The condition j <= i must hold, if in target string the character is found at index i and in start string it is found at index j.
      • This is because the ‘R’ character can only move to the right in the start string. Hence, if i > j, it means the ‘R’ character cannot move to its corresponding position in target, and we should return false.
  4. Simultaneous Comparison:
    • Traverse through the start and target strings using indices i and j. Skip ‘_’ characters and check the positions of ‘L’ and ‘R’ to ensure they follow the above movement rules.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java
class Solution {
    public boolean canChange(String start, String target) {
        if (!start.replace("_", "").equals(target.replace("_", ""))) {
            return false;
        }
        int i = 0, j = 0, 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)) {
                return false;
            }
            if (j == n) {
                break;
            }
            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++;
        }
        return true;
    }
}
Python
class Solution:
    def canChange(self, start: str, target: str) -> bool:
        if start.replace('_', '') != target.replace('_', ''):
            return False
        i = 0
        j = 0
        n = len(start)
        while i < n and j < n:
            # Skip underscores in both strings
            while i < n and start[i] == '_':
                i += 1
            while j < n and target[j] == '_':
                j += 1                
            # Ensure constraints are maintained between positions
            if (i < n) != (j < n):
                return False
            if j == n:
                break
            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
        return True

Complexity

  • ⏰ Time complexity: O(n) - We only need to traverse the strings start and target once.
  • 🧺 Space complexity: O(1) - We use a constant amount of extra space, aside from the input strings.