How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at MathWorks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at MathWorks during technical interviews.

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.

Input: ("abc", "bca")

Expected Output: 1

Explanation: Keep 'bc' (a prefix subsequence of t = 'bca') and move 'a' to the end: 'abc' -> 'bca'. One move.

Input: ("abc", "cab")

Expected Output: 2

Explanation: Longest prefix of t='cab' that is a subsequence of s='abc' is 'ab' (length 2), so n - 2 = 1? No: 'ab' is not a prefix of 'cab'. The longest prefix of 'cab' that is a subsequence of 'abc' is just 'c'... 'c' appears, then 'a' after it does not, so length 1, giving 3-1=2. Move 'a' then 'b' to the end.

Input: ("aab", "aba")

Expected Output: 1

Explanation: Keep 'ab' (prefix subsequence of 'aba') and move the second 'a' to the end: 'aab' -> 'aba'. One move.

Input: ("abab", "baba")

Expected Output: 1

Explanation: Keep 'bab' as a prefix subsequence of t='baba' and move the leading 'a' to the end. One move.

Input: ("ab", "cd")

Expected Output: -1

Explanation: s and t are not anagrams, so transformation is impossible.

Input: ("a", "a")

Expected Output: 0

Explanation: Single identical character requires no moves.

Input: ("", "")

Expected Output: 0

Explanation: Empty strings are trivially equal; 0 moves.

Input: ("aaaa", "aaaa")

Expected Output: 0

Explanation: All characters identical; already equal.

Input: ("abcde", "edcba")

Expected Output: 4

Explanation: Full reversal: only the single character 'e' can be kept as the prefix of t, so 5 - 1 = 4 moves.

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.

Quick Overview

This question evaluates a candidate's understanding of string manipulation, permutation feasibility, and algorithmic optimization for computing minimal move counts.