Problem

In a string composed of L, R, and X characters, like RXXLRXRXL, a move consists of either replacing one occurrence of XL with LX, or replacing one occurrence of RX with XR. Given the starting string start and the ending string end, return True if and only if there exists a sequence of moves to transform one string to the other.

Source: https://leetcode.com/problems/swap-adjacent-in-lr-string

Constraints

• 1 <= start.length <= 10^4
• start.length == end.length
• Both start and end will only consist of characters in L, R, and X

Asymptotic Complexity

• Time: O(n), visits each element
• Space: O(1), balanced L and R counts

Strategy

• Scan both arrays to balance the L and R counts
• X can be ignored entirely
• To move left 0 or more times, L must occur in the END array first:
  • Exit if the R count is not balanced i.e., r != 0
  • Increase l when found in END
  • Decrease l when found in START
  • Exit if l becomes negative i.e., 0 <= l < n
• To move right 0 or more times, R must occur in the START array first:
  • Exit if the L count is not balanced i.e., l != 0
  • Increase r when found in START
  • Decrease r when found in END
  • Exit if r becomes negative i.e., 0 <= r < n
• The transform is valid when both counts are balanced i.e., l == 0 and r == 0

Implementation

class Solution {
public:
    bool canTransform(string start, string end) {
        int16_t l{0};
        int16_t r{0};
        for (int16_t i = 0; i < start.length(); ++i) {
            if ((start[i] == 'L' && r > 0) ||
                (end[i] == 'R' && l > 0)) {
                return false;
            }

            l += end[i] == 'L' ? 1 : 0;
            l -= start[i] == 'L' ? 1 : 0;
            r += start[i] == 'R' ? 1 : 0;
            r -= end[i] == 'R' ? 1 : 0;
            if (l < 0 || r < 0) {
                return false;
            }
        }

        return l == 0 && r == 0;
    }
};