Introduction

String transformation problems are common in coding interviews because they test how well we can identify patterns instead of directly simulating every operation.

In this problem, we are given two strings of the same length. The only allowed operation is to pick any character from the string and move it to the beginning.

Our goal is to find the minimum number of operations required to transform s1 into s2. If the transformation is impossible, we return -1.

The key idea is to avoid actually performing the operations. Instead, we compare the strings from right to left and find the longest suffix that can remain unchanged.

1. Problem Statement

Given two strings s1 and s2, transform s1 into s2 using the following operation:

Pick any character from s1 and move it to the beginning of the string.

Return the minimum number of operations required.

If it is impossible to transform s1 into s2, return -1.

Example 1

Code
s1 = "abd"
s2 = "bad"

Move b to the beginning:

Code
abd
↓
bad

Therefore:

Code
Output = 1

Example 2

Code
s1 = "GeeksForGeeks"
s2 = "ForGeeksGeeks"

The characters F, o, and r need to be moved to the beginning.

Therefore:

Code
Output = 3

2. Key Observation

The important property of this operation is that moving a character to the beginning does not change the relative order of the characters that are not moved.

For example:

Code
s1 = "abcdef"

If we move d to the beginning:

Code
dabcef

The remaining characters are still in the same relative order:

Code
a → b → c → e → f

Because of this, we don't need to simulate every operation.

Instead, we can find the longest suffix of s1 that already matches the corresponding suffix of s2.

The characters outside that suffix are the ones that need to be moved.

3. Why Do We Compare From the End?

Consider:

Code
s1 = "abd"
s2 = "bad"

Start from the right:

Code
s1: a b d
        ↑

s2: b a d
        ↑

The characters are equal:

Code
d == d

So d can remain where it is.

Move both pointers backward:

Code
s1: a b
      ↑

s2: b a
      ↑

Now:

Code
b != a

This means b cannot remain in this position. It must be moved to the beginning.

So:

Code
answer = 1

This is the central idea behind the solution.

4. Greedy Approach

We use two pointers:

Java
int i = s1.length() - 1;
int j = s2.length() - 1;

Both pointers start at the end of their respective strings.

When the characters match

If:

Java
s1.charAt(i) == s2.charAt(j)

the characters can remain in their relative positions.

So we move both pointers:

Java
i--;
j--;

When the characters don't match

If:

Java
s1.charAt(i) != s2.charAt(j)

the current character from s1 must be moved to the beginning.

Therefore:

Java
res++;
i--;

Notice that j does not move.

We still need to find a character earlier in s1 that matches s2[j].

5. First Check the Length

The operation only rearranges characters. It cannot add or remove characters.

Therefore, strings with different lengths cannot be transformed into each other.

Java
if (s1.length() != s2.length()) {
    return -1;
}

For example:

Code
s1 = "abc"
s2 = "abcd"

The transformation is impossible.

So the result is:

Code
-1

6. Check Character Frequencies

The two strings must also contain exactly the same characters with the same frequencies.

We can use a frequency array:

Java
int[] count = new int[256];

For every character in s1, increase its count:

Java
count[s1.charAt(i)]++;

For every character in s2, decrease its count:

Java
count[s2.charAt(i)]--;

For example:

Code
s1 = "abd"
s2 = "bad"

Both strings contain:

Code
a → 1
b → 1
d → 1

Therefore, all counts become zero.

If any count is not zero, the strings contain different characters and the transformation is impossible.

Java
for (int i = 0; i < 256; i++) {
    if (count[i] != 0) {
        return -1;
    }
}

For example:

Code
s1 = "abc"
s2 = "abd"

c exists in s1, but not in s2.

Therefore:

Code
Output = -1

7. Complete Java Solution

Java
class Solution {

    int transform(String s1, String s2) {

        // Step 1: Lengths must be equal
        if (s1.length() != s2.length()) {
            return -1;
        }

        int n = s1.length();

        // Step 2: Check character frequencies
        int[] count = new int[256];

        for (int i = 0; i < n; i++) {
            count[s1.charAt(i)]++;
            count[s2.charAt(i)]--;
        }

        // If frequencies are different,
        // transformation is impossible
        for (int i = 0; i < 256; i++) {
            if (count[i] != 0) {
                return -1;
            }
        }

        // Step 3: Compare from right to left
        int i = n - 1;
        int j = n - 1;
        int res = 0;

        while (i >= 0 && j >= 0) {

            // Characters are different.
            // s1[i] needs to be moved to the front.
            if (s1.charAt(i) != s2.charAt(j)) {
                res++;
                i--;
            }
            // Characters match, so both can remain
            // in their relative positions.
            else {
                i--;
                j--;
            }
        }

        return res;
    }
}

8. Understanding the Main Logic

The most important part of the solution is:

Java
while (i >= 0 && j >= 0) {

    if (s1.charAt(i) != s2.charAt(j)) {
        res++;
        i--;
    } else {
        i--;
        j--;
    }
}

There are only two possibilities.

Characters Match

Java
s1.charAt(i) == s2.charAt(j)

Both characters can stay in place relative to the other preserved characters.

Java
i--;
j--;

Characters Don't Match

Java
s1.charAt(i) != s2.charAt(j)

The character from s1 cannot be part of the preserved suffix.

So we count one operation:

Java
res++;
i--;

We don't move j because s2[j] still needs to be matched.

9. Dry Run

Consider:

Code
s1 = "abd"
s2 = "bad"

Initially:

Code
i = 2
j = 2
res = 0

Comparison 1

Code
s1[2] = d
s2[2] = d

They match.

Code
i = 1
j = 1
res = 0

Comparison 2

Code
s1[1] = b
s2[1] = a

They don't match.

So b needs to be moved to the beginning:

Code
res = 1
i = 0
j = 1

Comparison 3

Code
s1[0] = a
s2[1] = a

They match.

Code
i = -1
j = 0

The process is complete.

Final result:

Code
1

10. Another Example

Consider:

Code
s1 = "abc"
s2 = "cab"

Start from the right:

Code
s1: a b c
        ↑

s2: c a b
        ↑

c != b.

Therefore, c must be moved:

Code
res = 1
i--

Now:

Code
s1: a b
      ↑

s2: c a b
      ↑

b != a.

Therefore:

Code
res = 2
i--

Now:

Code
s1: a
     ↑

s2: c a b
    ↑

a == a.

So:

Code
i--
j--

Final result:

Code
2

The transformation can be performed as:

Code
abc
bca    // move b to the front
cba    // move c to the front

So the minimum number of operations is:

Code
2

11. Why Does j Stay When Characters Don't Match?

This is an important interview question.

Suppose:

Code
s1 = "abc"
s2 = "cab"

At the first comparison:

Code
s1[i] = c
s2[j] = b

They don't match.

We cannot simply move both pointers because b in s2 still needs to be matched.

There may be an earlier character in s1 that matches it.

Therefore:

Java
res++;
i--;

but:

Java
j

stays unchanged.

This allows us to search backward in s1 until we find the character needed by s2.

12. Why the Greedy Approach Works

Every operation moves one character to the beginning.

Therefore, characters that are not moved must preserve their relative order.

The best possible strategy is to preserve the longest suffix of s1 that already matches the suffix of s2.

Starting from the right allows us to identify this suffix directly:

Code
Matching character
       ↓
Keep it

Non-matching character
       ↓
Move it to the front

So the minimum number of operations is the number of characters that cannot be included in this matching suffix.

In other words:

Code
Minimum Operations
=
Characters that must be moved to the front

13. Complexity Analysis

Let n be the length of the strings.

Time Complexity

Checking the character frequencies takes:

Code
O(n)

The right-to-left traversal also takes:

Code
O(n)

Therefore:

Code
Overall Time Complexity = O(n)

Auxiliary Space

We use a fixed-size frequency array:

Java
int[] count = new int[256];

Since its size is constant:

Code
Auxiliary Space = O(1)

So the final complexity is:

Code
Time:  O(n)
Space: O(1)

14. Important Interview Takeaway

The main trick is to avoid actually performing the operations.

Instead:

  1. Check that both strings have the same length.

  2. Check that they contain the same characters.

  3. Start comparing both strings from the right.

  4. Keep matching characters as part of the unchanged suffix.

  5. Count every non-matching character from s1 as one operation.

  6. Return the total count.

The core logic is:

Java
if (s1.charAt(i) != s2.charAt(j)) {
    res++;
    i--;
} else {
    i--;
    j--;
}

This gives an efficient O(n) time and O(1) auxiliary space solution without explicitly performing the string transformations.

Summary

The key observation is that moving a character to the beginning does not change the relative order of the characters left behind. Therefore, we can preserve the longest matching suffix of the two strings and count the remaining characters as required moves.

This turns what looks like a simulation problem into a simple greedy two-pointer problem. The approach is efficient, easy to implement, and useful for similar string-transformation problems in coding interviews.