2337.Move Pieces to Obtain a String.md

Difficulty	Medium
Source	Daily-Question (POTD 05-Dec)
Tags	Strings Two Pointers

🚀 2337 - Move Pieces to Obtain a String 🧠

Problem Link:

LeetCode - Move Pieces to Obtain a String

💡 Problem Breakdown:

We are tasked to determine if the target string can be formed by rearranging pieces ('L' and 'R') from the start string. The following rules apply:

• L can move only to the left if there is a blank space ('_') directly on its left.
• R can move only to the right if there is a blank space ('_') directly on its right.
• '_' can accommodate any piece but cannot move itself.

The main constraints are:

1. The order of the pieces must remain the same for both strings.
2. The relative movement of 'L' and 'R' must adhere to their respective movement rules.

🔍 Example Walkthrough:

Example 1:

Input:
start = "_L__R__R_"
target = "L______RR"

Output:
true

Explanation:

• Move the first 'L' one step to the left: _L__R__R_ → L___R__R_
• Move the last 'R' one step to the right: L___R__R_ → L___R___R
• Move the second 'R' three steps to the right: L___R___R → L______RR

Thus, it is possible to transform start into target.

Example 2:

Input:
start = "R_L_"
target = "__LR"

Output:
false

Explanation:

• The 'R' in start moves to the right, making _RL_.
• No further moves can transform it into __LR.

Thus, the output is false.

🧠 Approach:

1. Key Observations:

1. The count of 'L', 'R', and '_' must be the same in both strings, or the transformation is immediately invalid.
2. Both strings must have the same relative order of 'L' and 'R', ignoring underscores ('_').
3. 'L' in start must always move leftward, and its position in start must be greater than or equal to its position in target.
4. 'R' in start must always move rightward, and its position in start must be less than or equal to its position in target.

2. Simulation with Two Pointers:

We can simulate the movement of pieces using two pointers, one for start and one for target:

1. Traverse start and target while skipping blanks ('_').
2. For each matching piece:
   • If it is 'L', ensure start_index >= target_index.
   • If it is 'R', ensure start_index <= target_index.
3. If all checks pass, return true; otherwise, return false.

🕒 Time Complexity:

• O(n): Each character in start and target is processed once.
• Space Complexity:
  • O(1): No additional space apart from variables.

📝 Solution Code

Code (C):

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

    for (int k = 0; k < n; k++) {
        if (start[k] != '_') {
            while (j < n && target[j] == '_') j++;

            if (j == n || start[k] != target[j]) return false;

            if ((start[k] == 'L' && k < j) || (start[k] == 'R' && k > j)) return false;

            j++;
        }
    }

    while (j < n) {
        if (target[j] != '_') return false;
        j++;
    }

    return true;
}

Code (C++)

class Solution {
public:
    bool canChange(string start, string target) {
        int n = start.size();
        int j = 0;

        for (int i = 0; i < n; ++i) {
            if (start[i] != '_') {
                while (j < n && target[j] == '_') j++;

                if (j == n || start[i] != target[j]) return false;

                if ((start[i] == 'L' && i < j) || (start[i] == 'R' && i > j)) return false;

                j++;
            }
        }

        while (j < n) {
            if (target[j] != '_') return false;
            j++;
        }

        return true;
    }
};

Code (Java)

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

        for (int i = 0; i < n; i++) {
            if (start.charAt(i) != '_') {
                while (j < n && target.charAt(j) == '_') j++;

                if (j == n || start.charAt(i) != target.charAt(j)) return false;

                if ((start.charAt(i) == 'L' && i < j) || (start.charAt(i) == 'R' && i > j)) return false;

                j++;
            }
        }

        while (j < n) {
            if (target.charAt(j) != '_') return false;
            j++;
        }

        return true;
    }
}

Code (Python)

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        if start.replace('_', '') != target.replace('_', ''):
            return False
        
        n = len(start)
        i, j = 0, 0

        for i in range(n):
            if start[i] != '_':
                while target[j] == '_':
                    j += 1
                
                if (start[i] == 'L' and i < j) or (start[i] == 'R' and i > j):
                    return False
                
                j += 1

        return True

Code (Rust)

impl Solution {
    pub fn can_change(start: String, target: String) -> bool {
        let n = start.len();
        let (mut i, mut j) = (0, 0);
        let start_chars: Vec<char> = start.chars().collect();
        let target_chars: Vec<char> = target.chars().collect();

        while i < n {
            if start_chars[i] != '_' {
                while j < n && target_chars[j] == '_' {
                    j += 1;
                }

                if j == n || start_chars[i] != target_chars[j] {
                    return false;
                }

                if (start_chars[i] == 'L' && i < j) || (start_chars[i] == 'R' && i > j) {
                    return false;
                }

                j += 1;
            }
            i += 1;
        }

        while j < n {
            if target_chars[j] != '_' {
                return false;
            }
            j += 1;
        }

        true
    }
}

🎯 Contribute or Ask Questions:

For more discussions, questions, or help with the solution, feel free to reach out on LinkedIn: Connect with Me!.

Enjoying the Solution?

If this helped you, please star this repo to support the efforts and keep it growing!