Determine string transform via end-append moves

Given two strings s and t of equal length over lowercase English letters, in one move you may delete any character from s and append it to the end of s. Determine whether s can be transformed into t using such moves, and if so, return the minimum number of moves. Explain your algorithm, prove correctness, analyze complexity, and provide code in C, C++, Java, or JavaScript.

Determine string transform via end-append moves

You are given two strings s and t of equal length consisting of lowercase English letters. In one move you may delete any single character from s and append it to the end of s. Determine whether s can be transformed into t using these moves, and if so, return the minimum number of moves required. If it is impossible, return -1.

Key idea: a transformation is possible only if s and t are anagrams (same multiset of characters). The characters you choose NOT to move keep their original relative order and must form a prefix of t matched in order; every other character is appended to the end (in some order you control, so they can always be arranged to complete t). Therefore the minimum number of moves equals n minus the length of the longest prefix of t that appears as a subsequence of s. Use a greedy two-pointer scan: walk through s, advancing a pointer j into t each time s[i] == t[j]; the answer is n - j.

Example: s = "abc", t = "cab". Matching greedily keeps only c... actually keeping ab as a prefix subsequence and moving c then... the optimal is to move a then b, giving 2 moves -> answer 2.

Constraints

• 1 <= s.length == t.length (the empty string is also handled and returns 0)
• s and t consist only of lowercase English letters ('a'-'z')
• If s and t are not anagrams, no sequence of moves can succeed; return -1

Hints

1. A move never changes the multiset of characters in s, so a transformation is possible only when s and t are anagrams. Check this first; otherwise return -1.
2. The characters you do NOT move stay in their original relative order. Think about which characters can be 'kept' and what constraint they must satisfy with respect to t.
3. The kept characters must match a prefix of t read left-to-right; every other character gets appended to the end (and you can append them in whatever order you need). So minimize moves by maximizing the kept prefix: find the longest prefix of t that is a subsequence of s using a greedy two-pointer scan, and return n minus its length.