Determine string transform via end-append moves
Company: MathWorks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
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.
Quick Answer: This question evaluates a candidate's understanding of string manipulation, permutation feasibility, and algorithmic optimization for computing minimal move counts.
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
Examples
Input: ("abc", "abc")
Expected Output: 0
Explanation: s already equals t, so 0 moves are needed.
Input: ("ab", "ba")
Expected Output: 1
Explanation: Move 'a' to the end: 'ab' -> 'ba'. One move.
Hints
- 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.
- 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.
- 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.