Transform String

Problem Overview

You may only pick a character in s1 and move it to the front.

Intuition

You may only pick a character in s1 and move it to the front. That means any suffix of s2 that already appears in order as a subsequence of s1 can stay put - everything else has to be moved. First confirm the two strings are anagrams (otherwise impossible). Then walk both from the right: whenever s1 does not match the next needed s2 char, that s1 char will need a move later, so bump the cost and keep scanning left in s1 until the match lines up again.

Algorithm

1If lengths differ, return -1.
2Build a 256-slot frequency table: +1 for s1, -1 for s2. Any leftover non-zero means not anagrams -> -1.
3Set i = j = n-1 and ops = 0.
4While i >= 0: while s1[i] != s2[j], ops++, i--. When they match, step both left.
5Return ops.

Example Walkthrough

Input: s1 = "ABCD", s2 = "CBAD"

1. Frequencies match, so a transform exists.
2. From the right, D matches D. Then C vs A mismatch - skip C and B in s1 (2 moves) until A matches A.
3. B matches B. Cost is 2.

Output: 2

Common Pitfalls

• Always check anagrams first - unequal letter bags can never become each other under this operation.
• Scan from the right; a left-to-right greedy misses how move-to-front reshapes prefixes.
• Only count mismatches in s1 while hunting for s2[j] - do not move j until you have a match.
• Same length alone is not enough; character multisets must match too.

Transform String.java

Java

// Approach: Only possible if s1 and s2 are anagrams (same char frequencies).
// Allowed op: pick a char in s1 and move it to the front. Matching from the
// right, every mismatched s1 char must be moved later, so count those skips
// until s1 aligns with the remaining suffix of s2.
// Complexity: O(n) time and O(1) space.
class Solution {

    int transform(String s1, String s2) {
        int n = s1.length();
        if (n != s2.length()) {
            return -1;
        }

        int[] freq = new int[256];
        for (int i = 0; i < n; i++) {
            freq[s1.charAt(i)]++;
            freq[s2.charAt(i)]--;
        }
        for (int f : freq) {
            if (f != 0) {
                return -1;
            }
        }

        int i = n - 1;
        int j = n - 1;
        int ops = 0;
        while (i >= 0) {
            while (i >= 0 && s1.charAt(i) != s2.charAt(j)) {
                ops++;
                i--;
            }
            if (i >= 0) {
                i--;
                j--;
            }
        }
        return ops;
    }
}

Was this solution helpful?