2337. Move Pieces to Obtain a String

Time: O(n)

Space: O(1)

Intuition

Check if you can reach destination with k-1 moves and 1 final step. From position x with k moves: can reach positions x-k+1 to x (move left any amount, then step right).

Algorithm

1Check if |target - source| <= k and (k - |target - source|) % 2 == 0.

Common Pitfalls

•Must use exactly k moves. After reaching target, must have even remaining moves to waste in place.

2337.cs

// Approach: Two-pointer matching non-blank chars; 'L' can only move left, 'R' only right.
// Time: O(n) Space: O(1)

public class Solution
{
    public bool CanChange(string start, string target)
    {
        int length = start.Length;
        int startIndex = 0; // start's index
        int targetIndex = 0; // target's index

        while (startIndex <= length && targetIndex <= length)
        {
            while (startIndex < length && start[startIndex] == '_')
                ++startIndex;
            while (targetIndex < length && target[targetIndex] == '_')
                ++targetIndex;
            if (startIndex == length || targetIndex == length)
                return startIndex == length && targetIndex == length;
            if (start[startIndex] != target[targetIndex])
                return false;
            if (start[startIndex] == 'R' && startIndex > targetIndex)
                return false;
            if (start[startIndex] == 'L' && startIndex < targetIndex)
                return false;
            ++startIndex;
            ++targetIndex;
        }

        return true;
    }
}

Was this solution helpful?