algoadvance

Leetcode 777. Swap Adjacent in LR String

Problem Statement

Let’s consider a string s that is composed of the characters ‘L’, ‘R’, and ‘X’. In one move, any adjacent two characters can be swapped if and only if one of the conditions is met:

• If ‘X’ is adjacent to an ‘L’, and ‘L’ is on the right of ‘X’, then ‘L’ and ‘X’ can be swapped.
• If ‘X’ is adjacent to an ‘R’, and ‘R’ is on the left of ‘X’, then ‘R’ and ‘X’ can be swapped.

You are given two strings start and end of the same length and consisting only of the characters ‘L’, ‘R’, and ‘X’. Your task is to determine if it is possible to transform start into end by performing any number of moves. Return true if possible, otherwise return false.

Clarifying Questions

1. Q: Can start and end be empty strings? A: No, both start and end will have at least one character.

2. Q: Are the lengths of start and end guaranteed to be the same? A: Yes, both strings will have the same length.

3. Q: Do the strings only consist of the characters ‘L’, ‘R’, and ‘X’? A: Yes, both strings will only contain ‘L’, ‘R’, and ‘X’.

4. Q: Is it possible to have multiple sequences of moves to transform start to end? A: Yes, but if there’s at least one sequence of valid moves that achieves the transformation, the output should be true.

Strategy

To solve this problem, we need to:

1. Ensure both strings start and end have the same number of ‘L’ and ‘R’ characters in the same order. Ignore the ‘X’ characters for this part.
2. When L and R are present in the same order in both start and end, we need to check their valid movements:
   • ‘L’ can only move to the left, so for every ‘L’ in end, we must find it in start at the same position or to the left.
   • ‘R’ can only move to the right, so for every ‘R’ in end, we must find it in start at the same position or to the right.

Code

public class SwapAdjacentLRString {
    public boolean canTransform(String start, String end) {
        if (start.length() != end.length()) return false;

        // Filter out 'X' from both strings and compare the resultant strings
        String filteredStart = start.replace("X", "");
        String filteredEnd = end.replace("X", "");
        
        if (!filteredStart.equals(filteredEnd)) return false;

        // Now check the valid movements
        int p1 = 0, p2 = 0;
        int n = start.length();
        while (p1 < n && p2 < n) {
            // Skip 'X' in both strings
            while (p1 < n && start.charAt(p1) == 'X') p1++;
            while (p2 < n && end.charAt(p2) == 'X') p2++;

            // If we reached the end in either string
            if (p1 == n || p2 == n) return p1 == p2;

            // If the characters are different
            if (start.charAt(p1) != end.charAt(p2)) return false;

            // Check the movement constraints
            if (start.charAt(p1) == 'L' && p1 < p2) return false;
            if (start.charAt(p1) == 'R' && p1 > p2) return false;

            // Move to the next character
            p1++;
            p2++;
        }

        return true;
    }

    public static void main(String[] args) {
        SwapAdjacentLRString solution = new SwapAdjacentLRString();
        System.out.println(solution.canTransform("RXXLRXRXL", "XRLXXRRLX")); // true
        System.out.println(solution.canTransform("X", "L")); // false
    }
}

Time Complexity

• Filtering and comparing strings: O(n)
• Checking valid movements: O(n)

Overall, the time complexity is O(n) where n is the length of the strings.

Explanation

1. We first filter out ‘X’ and compare the resultant strings to check the order of ‘L’ and ‘R’.
2. We then iterate through both strings, ensuring ‘L’ doesn’t move right and ‘R’ doesn’t move left, and validate their positions.

This ensures that all conditions are met for a valid transformation.

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?