Move L and R Characters

XXX. Move L and R Characters

String

Two Pointer

Problem Statement:

Given two strings start and target, determine if it's possible to transform the start string into the target string. The rules for transformation are:

• 'L' can only move left by swapping with '_'
• 'R' can only move right by swapping with '_'
• '_' represents an empty space
• The relative order of Ls and Rs must remain the same

Algorithm:

1. **Initial Check**:
   • Remove all '_' from both strings
   • Compare remaining characters - must be identical
2. **Two Pointer Approach**:
   • Skip '_' characters in both strings
   • Compare positions of corresponding L and R
   • Check if movement is valid based on relative positions
3. **Movement Rules**:
   • 'L' in start must be at same or higher index than target
   • 'R' in start must be at same or lower index than target

Complexity:

Time Complexity: O(n), where n is the length of strings
Space Complexity: O(1)

Implementation:

Java Solution:

public boolean canChange(String start, String target) {
    if (!start.replaceAll("_", "").equals(target.replaceAll("_", "")))   // Check if same chars
        return false;
    
    for (int i = 0, j = 0, n = start.length(); i < n && j < n; i++, j++) {
        while (i < n && start.charAt(i) == '_') i++;          // Skip spaces in start
        while (j < n && target.charAt(j) == '_') j++;         // Skip spaces in target
        
        // Check invalid moves: L can't move right, R can't move left
        if (i < n && j < n && (start.charAt(i) == 'L' && i < j || 
                              target.charAt(j) == 'R' && i > j))
            return false;
    }
    return true;
}
                

Python Solution:

def canChange(self, start: str, target: str) -> bool:
    if start.replace('_', '') != target.replace('_', ''):     # Check if same chars
        return false
    
    n = len(start)
    i = j = 0
    
    while i < n and j < n:
        while i < n and start[i] == '_': i += 1               # Skip spaces in start
        while j < n and target[j] == '_': j += 1              # Skip spaces in target
        
        # Check for end of strings
        if i == n or j == n: return i == n and j == n
        
        # Check invalid moves: L can't move right, R can't move left
        if (start[i] == 'L' and i < j) or (target[j] == 'R' and i > j):
            return False
            
        i += 1
        j += 1
    
    return i == n and j == n
                

C++ Solution:

bool canChange(string start, string target) {
    string s1 = start, s2 = target;
    s1.erase(remove(s1.begin(), s1.end(), '_'), s1.end());   // Remove spaces
    s2.erase(remove(s2.begin(), s2.end(), '_'), s2.end());
    if (s1 != s2) return false;                              // Check if same chars
    
    int n = start.length();
    for (int i = 0, j = 0; i < n && j < n; i++, j++) {
        while (i < n && start[i] == '_') i++;                // Skip spaces in start
        while (j < n && target[j] == '_') j++;               // Skip spaces in target
        
        // Check invalid moves: L can't move right, R can't move left
        if (i < n && j < n && (start[i] == 'L' && i < j || 
                              target[j] == 'R' && i > j))
            return false;
    }
    return true;
}
                

Explanation:

• **Initial Validation**:
  • Remove all spaces and compare remaining characters
  • This ensures same number and order of L and R
• **Two Pointer Logic**:
  • Skip spaces to find next actual character in both strings
  • Compare positions to ensure valid moves
  • L can only move left (i >= j)
  • R can only move right (i <= j)
• **Position Rules**:
  • For 'L': current position must be >= target position
  • For 'R': current position must be <= target position
  • These ensure characters can reach their target positions