240. Transform One String to Another Using Minimum Number of Given Operation

You're given two strings A and B. The only operation allowed is: remove any single character from A and reinsert it at the very front of A. Find the minimum number of such operations needed to make A equal to B. If A and B are not anagrams of each other (don't contain exactly the same multiset of characters), no number of operations can ever make them equal - print -1.

Input: The first line contains string A. The second line contains string B. Output: Print a single integer - the minimum number of front-insertion operations needed to transform A into B, or -1 if impossible.

1 <= |A|, |B| <= 2000

The anagram check isn't just a nice-to-have edge case - it's a hard requirement, since the operation only REORDERS characters and never adds or removes any, so two strings with different character multisets can genuinely never be made equal.

You can repeatedly take any single character out of string A and move it to the very front. Find the minimum moves needed to turn A into B (or -1 if it's impossible). Brute force: Try every possible sequence of 'move to front' operations directly, exploring all orders - this branches combinatorially, impractical for anything beyond tiny strings. Optimised: The key insight is that the characters NOT moved always keep their original relative order from A - so checking whether progressively longer suffixes of B are valid subsequences of A (starting from the shortest possible suffix and growing) directly finds the minimum number of characters that must be moved, without ever simulating the actual moves.

After the same anagram check, repeatedly determine which single character currently needs to move to the front next (the one that lets the already-correctly-placed suffix grow), physically perform that move on a working copy of the string (remove the character and reinsert it at index 0), and increment an operation counter. Rescan the working string after each move to find the next character to relocate, repeating until the string matches B. Each simulated operation costs time proportional to the string length, so doing this up to n times is quadratic overall, but it directly mirrors the actual allowed operation rather than reasoning about it abstractly. Time: O(n^2) Space: O(n)

First confirm A and B are anagrams by comparing character frequencies (if not, answer -1). Otherwise, treat each distinct arrangement of A's characters as a node in an implicit graph where an edge represents one 'move a character to the front' operation, and run a breadth-first search from A's initial arrangement looking for the shortest sequence of moves that reaches B. This is guaranteed to find the true minimum by construction, but the number of distinct reachable string states can blow up combinatorially, making it impractical for anything but tiny strings. Time: Exponential (up to O(n!) states explored) Space: Exponential

First verify A and B are anagrams using a character frequency count over a fixed alphabet (otherwise print -1). Then walk a pointer j from the last character of A backward and a pointer i from the last character of B backward: whenever B[i] matches A[j], both pointers move back one step (that character already sits correctly relative to the others and never needs to move); whenever it doesn't match, only i moves back and a counter of needed moves is incremented. The final counter value is exactly the minimum number of move-to-front operations required, because only the characters that fail to already form a matching contiguous suffix (in relative order) ever need relocating. Time: O(n) Space: O(1) extra (beyond a fixed-size frequency array)

1. First check A and B are anagrams (contain exactly the same characters) - if not, print -1 immediately, since no number of moves could ever make them equal. 2. Realize that moving k characters to the front (in some chosen order) leaves the OTHER |A|-k characters behind, still in their original relative order within A - so those leftover characters, as they naturally sit in A, must exactly spell out the corresponding SUFFIX of B. 3. Try k = 0, 1, 2, ... in increasing order, checking each time whether B's suffix of length (|A|-k) is a valid subsequence of A - the smallest such k is the answer.

Time: O(n²) in the worst case - trying each possible k and checking a subsequence relationship (itself O(n)) for each. Space: O(1) extra space beyond the input strings themselves (a subsequence check just needs a couple of pointers).

A and B not anagrams of each other (-1); A already equal to B (0 operations); strings up to length 2000 for performance.

Be ready to explain clearly WHY the leftover (unmoved) characters must form a SUFFIX of B specifically (not just any subsequence) - this precise framing is the entire crux of the problem's clever reduction.