algoadvance

Leetcode 777. Swap Adjacent in LR String

Problem Statement

The problem statement can be found on LeetCode under the title “777. Swap Adjacent in LR String”. Below is a summary of the problem statement.

In a string composed of ‘L’, ‘R’, and ‘X’ characters:

• ‘L’ can move to the left one space.
• ‘R’ can move to the right one space.
• ‘X’ can swap with adjacent ‘L’ or ‘R’.

Given two strings start and end, determine if it’s possible to transform the start string into the end string using a finite number of moves.

Clarifying Questions

1. Are the strings always of the same length?
   • Yes, both start and end are of the same length.
2. Do the strings only contain the characters ‘L’, ‘R’, and ‘X’?
   • Yes, they contain only these three characters.
3. Is it guaranteed that the transformation is possible if the function returns true?
   • Yes, the function should return true only if it’s possible to transform start to end.

Strategy

1. Check Length and Characters: Ensure both strings are of the same length and contain the same set of characters when ‘X’ is ignored (since ‘X’ can be both present and moved around freely).

2. Double Pointer Technique:

   • Iterate through both strings using two pointers: i for start and j for end.
   • Skip all ‘X’ in both strings.
   • Compare start[i] with end[j]:
     • If the characters are different, return false.
     • If the characters are ‘L’, ensure i is not less than j because ‘L’ can only move left.
     • If the characters are ‘R’, ensure i is not greater than j because ‘R’ can only move right.

Code

Here’s the implementation of the strategy:

#include <iostream>
#include <string>

bool canTransform(std::string start, std::string end) {
    int n = start.size();
    
    int i = 0, j = 0;
    
    while (i < n || j < n) {
        // Skip all 'X' in start
        while (i < n && start[i] == 'X') i++;
        // Skip all 'X' in end
        while (j < n && end[j] == 'X') j++;
        
        // If both pointers reach the end
        if (i == n && j == n) return true;
        
        // If only one of them reaches the end
        if (i == n || j == n) return false;
        
        // If characters are not matching
        if (start[i] != end[j]) return false;
        
        // If characters are 'L'
        if (start[i] == 'L' && i < j) return false;
        
        // If characters are 'R'
        if (start[i] == 'R' && i > j) return false;
        
        // Move both pointers
        i++;
        j++;
    }
    
    return true;
}

int main() {
    std::string start = "RXXLRXRXL";
    std::string end = "XRLXXRRLX";
    bool result = canTransform(start, end);
    
    std::cout << (result ? "True" : "False") << std::endl;
    
    return 0;
}

Time Complexity

The time complexity of this approach is O(n) where n is the length of the strings because we are essentially traversing each string once with our pointers.

Explanation

• We maintain two pointers i and j to traverse start and end, respectively.
• We skip over ‘X’ since they can freely move and swap with ‘L’ and ‘R’.
• We compare ‘L’ and ‘R’ at each non-‘X’ character to ensure they follow the move constraints.
• If any constraint is violated, we return false; otherwise, we continue and eventually return true if all conditions are satisfied.

This ensures an efficient check in linear time with respect to the length of the strings.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?