Rotating Substrings
Contest: Codeforces Round 646 (Div. 2)
Difficulty rating: 2600
Tags: dp, strings

You are given two strings $$$s$$$ and $$$t$$$, each of length $$$n$$$ and consisting of lowercase Latin alphabets. You want to make $$$s$$$ equal to $$$t$$$.

You can perform the following operation on $$$s$$$ any number of times to achieve it —

- Choose any substring of $$$s$$$ and rotate it clockwise once, that is, if the selected substring is $$$s[l,l+1...r]$$$, then it becomes $$$s[r,l,l + 1 ... r - 1]$$$. All the remaining characters of $$$s$$$ stay in their position. For example, on rotating the substring $$$[2,4]$$$ , string "abcde" becomes "adbce".

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Find the minimum number of operations required to convert $$$s$$$ to $$$t$$$, or determine that it's impossible.

Input format:
The first line of the input contains a single integer $$$t$$$ $$$(1\leq t \leq 2000)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1\leq n \leq 2000)$$$ — the length of the strings.

The second and the third lines contain strings $$$s$$$ and $$$t$$$ respectively.

The sum of $$$n$$$ over all the test cases does not exceed $$$2000$$$.

Output format:
For each test case, output the minimum number of operations to convert $$$s$$$ to $$$t$$$. If it is not possible to convert $$$s$$$ to $$$t$$$, output $$$-1$$$ instead.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the $$$1$$$-st test case, since $$$s$$$ and $$$t$$$ are equal, you don't need to apply any operation.

For the $$$2$$$-nd test case, you only need to apply one operation on the entire string ab to convert it to ba.

For the $$$3$$$-rd test case, you only need to apply one operation on the entire string abc to convert it to cab.

For the $$$4$$$-th test case, you need to apply the operation twice: first on the entire string abc to convert it to cab and then on the substring of length $$$2$$$ beginning at the second character to convert it to cba.

For the $$$5$$$-th test case, you only need to apply one operation on the entire string abab to convert it to baba.

For the $$$6$$$-th test case, it is not possible to convert string $$$s$$$ to $$$t$$$.

Example input:
6
1
a
a
2
ab
ba
3
abc
cab
3
abc
cba
4
abab
baba
4
abcc
aabc

Example output:
0
1
1
2
1
-1

Editorial:
Key Idea: We note that a clockwise rotation is the same as taking a character at any position in the string, and inserting it anywhere to it's left. Thus, we process the strings from the end, build the suffixes and move towards the prefix.
Detailed Explanation: The answer is $$$-1$$$ if both s and t do not have the same count of every character. Else, we can prove that it is always possible to convert s to t.
Now, let us remove the largest common suffix of both s and t. Now, using the key idea, we consider a move as picking a character at any position in s and inserting it to it's left. So, let us just "pick up" characters, and use them in any order as we iterate through s. Our total cost is equal to the number of characters we picked overall.
After removing common suffixes, suppose the last character of s is c. Since the last characters of s and t differ, we can pick up this c. Now, we want to make s[1,n-1] equal to t[1,n], given that we can insert c anywhere in s.
Let us consider dp[i][j] (only for when j $$$\geq$$$ i, which means that we want to make s[1,i] = t[1,j] by inserting some characters that we have picked. What characters can we pick? We can pick the characters whose count in s[i+1,n] > t[j+1,n]. The base case is dp[0][i] = 0. Now, let us write the transitions for this dp solution. Suppose that t[j] = x. There are three possible transitions from dp[i][j]:
1. If the count of x in s[i+1.n] is greater than it's count in t[j+1,n], then we can reach the state dp[i][j-1].
2. If s[i] = t[j], then we can reach the state dp[i-1][j-1].
3. We can pick up the character at position i (and insert it later) to reach dp[i-1][j] (with an additional cost of $$$1$$$).
The final answer is dp[n][n].
Time complexity: $$$O(N^2)$$$