Transform One String to Another using Minimum Number of Given Operation

The problem, simply

You get two words, A and B. There is only one move: pick any letter of A and put it at the very front of A. Find the smallest number of moves that turns A into B.

If it can never work, give back -1. That happens when the two words do not have exactly the same letters (same letters, same counts).

A story to remember it

Picture it

Examples

Way 1: the simple way

The kids who are never moved keep their old order and end up at the back. So they form the end of B, and they appear in A in the same order (maybe with other kids between them). In grown-up words, they are a suffix of B that is a subsequence of A.

1. First check that A and B have the same letters with the same counts. If not, return -1.
2. Try to keep keep = n kids, then n - 1, and so on.
3. For each keep, check if the last keep letters of B appear in A in order.
4. The first keep that works is the most kids you can leave alone. The answer is n - keep.

class Solution {
    public int transform(String A, String B) {
        if (!sameLetters(A, B)) return -1;
        int n = A.length();
        for (int keep = n; keep >= 0; keep--) {
            if (inOrder(B.substring(n - keep), A)) return n - keep;  // everyone else moves once
        }
        return n;
    }

    // do the letters of small appear in big, in the same order?
    private boolean inOrder(String small, String big) {
        int k = 0;
        for (int i = 0; i < big.length() && k < small.length(); i++) {
            if (big.charAt(i) == small.charAt(k)) k++;
        }
        return k == small.length();
    }

    private boolean sameLetters(String A, String B) {
        if (A.length() != B.length()) return false;
        int[] count = new int[256];
        for (char c : A.toCharArray()) count[c]++;
        for (char c : B.toCharArray()) count[c]--;
        for (int x : count) if (x != 0) return false;
        return true;
    }
}

How long it takes: up to n + 1 tries, each one a walk over A, O(n^2). Extra room: a fixed table of 256 counts, O(1).

Way 2: the clever way

Instead of trying every length, find the longest end of B in one walk. Put one finger i at the end of A and one finger j at the end of B, and walk left.

1. Check the letter counts. If they differ, return -1.
2. If A[i] equals B[j], that kid can stay. Move both fingers left.
3. If not, the kid at A[i] must be called to the front. Count one move, and move only i left.
4. When i falls off the left end, the count is the answer.

Keeping a kid as soon as it fits is always safe. Matching from the right and taking the first fit never uses up a letter that a longer match would have needed.

class Solution {
    public int transform(String A, String B) {
        int n = A.length();
        if (n != B.length()) return -1;
        int[] count = new int[256];
        for (char c : A.toCharArray()) count[c]++;
        for (char c : B.toCharArray()) count[c]--;
        for (int x : count) if (x != 0) return -1;   // different letters: impossible

        int moves = 0;
        int j = n - 1;                               // finger at the back of B
        for (int i = n - 1; i >= 0; i--) {           // finger at the back of A
            if (A.charAt(i) == B.charAt(j)) j--;     // this kid fits and stays
            else moves++;                            // this kid must go to the front
        }
        return moves;
    }
}

How long it takes: one walk over each word, O(n). Extra room: the fixed count table, O(1).

Watch out for

• Walking from the front. Kids who stay end up at the back, so the matching must start at the back.
• Moving j on a mismatch. On a mismatch only i moves, because that letter of A is the one that leaves.
• Skipping the count check. Without it, ABC and ABD would give 1 instead of -1.
• Lengths that differ. Return -1 right away.

What interviewers ask next

• Print the moves, not only the count. The kids that did not fit must form the front of B. Call them to the front in the reverse of that order.
• What if the move puts a letter at the back instead? Mirror the idea: walk from the front and keep the longest start of B that appears in A in order.
• What if you may move a letter anywhere? Then the kids who stay only need to keep their order, so the answer is n minus the longest common subsequence of A and B, which needs a 2D table.
• Why is greedy matching safe? Taking the rightmost possible match for each letter of B leaves the most room on the left for the letters still to match.

Remember this

Grown-up words: the kids who stay are the longest suffix of B that is a subsequence of A, the two fingers are two pointers, keeping the first fit is a greedy choice, and the letter counts are a frequency table.