Convert One String to Another with Constraints

Problem Overview

Both strings use A, B, and empty slots marked #.

Intuition

Both strings use A, B, and empty slots marked #. Letters keep their relative order: A can only slide left into empties, and B can only slide right. So after dropping the empties the two letter sequences must match, and each matched letter must be able to travel from its index in s1 to its index in s2 under those one-way moves. That means an A may not need to move right, and a B may not need to move left.

Algorithm

1Return false immediately when the lengths differ.
2Advance two pointers, skipping # in each string, so they land on the next letters.
3If one pointer runs out before the other, the letter counts differ, so return false.
4If the letters differ, return false.
5For A, reject when the s1 index is less than the s2 index. For B, reject when the s1 index is greater than the s2 index.
6Advance both pointers and repeat until both strings are exhausted.

Example Walkthrough

Input: s1 = "#A#B#", s2 = "A##B#"

1. Skipping empties, the first letters are both A at indices 1 and 0. A moves left, which is allowed.
2. The next letters are both B at indices 3 and 3, already in place.
3. Both pointers finish together, so the conversion is possible.

Output: true

Common Pitfalls

• Letters cannot pass each other. Matching only the multisets of A and B is not enough.
• An A that sits left of its target would have to move right, which is forbidden.
• A B that sits right of its target would have to move left, which is forbidden.
• Empty slots are free to fill from either side; only the letter indices matter for the move checks.

Convert One String to Another with Constraints.java

Java

// Approach: Treat '#' as empty slots. Walk both strings while skipping empties
// so letters are matched in order; the sequences must be identical. 'A' can
// only move left, so its index in s1 cannot be less than in s2. 'B' can only
// move right, so its index in s1 cannot be greater than in s2. Any violation
// of those position rules makes the conversion impossible.
// Complexity: O(n) time, O(1) extra space.
class Solution {
    public boolean isItPossible(String s1, String s2) {
        int n = s1.length();
        if (n != s2.length())
            return false;

        int i = 0, j = 0;
        while (true) {
            while (i < n && s1.charAt(i) == '#')
                i++;
            while (j < n && s2.charAt(j) == '#')
                j++;
            if (i == n || j == n)
                return i == n && j == n;

            char c = s1.charAt(i);
            if (c != s2.charAt(j))
                return false;
            if (c == 'A') {
                if (i < j)
                    return false;
            } else if (i > j) {
                return false;
            }
            i++;
            j++;
        }
    }
}

Was this solution helpful?