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
s1 = "abd"
s2 = "bad"
Move b to the beginning:
abd
↓
bad
Therefore:
Output = 1
Example 2
s1 = "GeeksForGeeks"
s2 = "ForGeeksGeeks"
The characters F, o, and r need to be moved to the beginning.
Therefore:
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:
s1 = "abcdef"
If we move d to the beginning:
dabcef
The remaining characters are still in the same relative order:
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:
s1 = "abd"
s2 = "bad"
Start from the right:
s1: a b d
↑
s2: b a d
↑
The characters are equal:
d == d
So d can remain where it is.
Move both pointers backward:
s1: a b
↑
s2: b a
↑
Now:
b != a
This means b cannot remain in this position. It must be moved to the beginning.
So:
answer = 1
This is the central idea behind the solution.
4. Greedy Approach
We use two pointers:
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:
s1.charAt(i) == s2.charAt(j)
the characters can remain in their relative positions.
So we move both pointers:
i--;
j--;
When the characters don't match
If:
s1.charAt(i) != s2.charAt(j)
the current character from s1 must be moved to the beginning.
Therefore:
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.
if (s1.length() != s2.length()) {
return -1;
}
For example:
s1 = "abc"
s2 = "abcd"
The transformation is impossible.
So the result is:
-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:
int[] count = new int[256];
For every character in s1, increase its count:
count[s1.charAt(i)]++;
For every character in s2, decrease its count:
count[s2.charAt(i)]--;
For example:
s1 = "abd"
s2 = "bad"
Both strings contain:
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.
for (int i = 0; i < 256; i++) {
if (count[i] != 0) {
return -1;
}
}
For example:
s1 = "abc"
s2 = "abd"
c exists in s1, but not in s2.
Therefore:
Output = -1
7. Complete Java Solution
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:
while (i >= 0 && j >= 0) {
if (s1.charAt(i) != s2.charAt(j)) {
res++;
i--;
} else {
i--;
j--;
}
}
There are only two possibilities.
Characters Match
s1.charAt(i) == s2.charAt(j)
Both characters can stay in place relative to the other preserved characters.
i--;
j--;
Characters Don't Match
s1.charAt(i) != s2.charAt(j)
The character from s1 cannot be part of the preserved suffix.
So we count one operation:
res++;
i--;
We don't move j because s2[j] still needs to be matched.
9. Dry Run
Consider:
s1 = "abd"
s2 = "bad"
Initially:
i = 2
j = 2
res = 0
Comparison 1
s1[2] = d
s2[2] = d
They match.
i = 1
j = 1
res = 0
Comparison 2
s1[1] = b
s2[1] = a
They don't match.
So b needs to be moved to the beginning:
res = 1
i = 0
j = 1
Comparison 3
s1[0] = a
s2[1] = a
They match.
i = -1
j = 0
The process is complete.
Final result:
1
10. Another Example
Consider:
s1 = "abc"
s2 = "cab"
Start from the right:
s1: a b c
↑
s2: c a b
↑
c != b.
Therefore, c must be moved:
res = 1
i--
Now:
s1: a b
↑
s2: c a b
↑
b != a.
Therefore:
res = 2
i--
Now:
s1: a
↑
s2: c a b
↑
a == a.
So:
i--
j--
Final result:
2
The transformation can be performed as:
abc
bca // move b to the front
cba // move c to the front
So the minimum number of operations is:
2
11. Why Does j Stay When Characters Don't Match?
This is an important interview question.
Suppose:
s1 = "abc"
s2 = "cab"
At the first comparison:
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:
res++;
i--;
but:
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:
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:
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:
O(n)
The right-to-left traversal also takes:
O(n)
Therefore:
Overall Time Complexity = O(n)
Auxiliary Space
We use a fixed-size frequency array:
int[] count = new int[256];
Since its size is constant:
Auxiliary Space = O(1)
So the final complexity is:
Time: O(n)
Space: O(1)
14. Important Interview Takeaway
The main trick is to avoid actually performing the operations.
Instead:
Check that both strings have the same length.
Check that they contain the same characters.
Start comparing both strings from the right.
Keep matching characters as part of the unchanged suffix.
Count every non-matching character from s1 as one operation.
Return the total count.
The core logic is:
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.
Join the conversation! Your thoughts help the community grow.