Rotating Substrings (Codeforces 1363F)
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: 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: 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.

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$$$.

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

Sample Outputs:
0
1
1
2
1
-1

Solution (Python):
import os
os_input = os.read(0, int(10000000.0)).split()
os_input_pos = -1
answer_list = []

def read_s():
    global os_input_pos
    os_input_pos += 1
    return os_input[os_input_pos].decode()

def read_i():
    return int(read_s())

def write_s(v):
    answer_list.append(v)

def write_i(v):
    write_s(str(v))

def print_ans():
    os.write(1, '\n'.join(answer_list).encode())
    os.write(1, '\n'.encode())
T = read_i()
while T:
    T -= 1
    n = read_i()
    s = read_s()
    t = read_s()
    if sorted(s) != sorted(t):
        write_i(-1)
        continue
    s_count = [[0 for i in range(n + 1)] for j in range(26)]
    t_count = [[0 for i in range(n + 1)] for j in range(26)]
    for i in range(n):
        for j in range(26):
            s_count[j][i] = s_count[j][i - 1]
            t_count[j][i] = t_count[j][i - 1]
        s_count[ord(s[i]) - ord('a')][i] += 1
        t_count[ord(t[i]) - ord('a')][i] += 1
    dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
    for i in range(0, n):
        for j in range(i, n):
            dp[i][j] = dp[i - 1][j] + 1
            if s[i] == t[j]:
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
            c = ord(t[j]) - ord('a')
            if s_count[c][i] < t_count[c][j]:
                dp[i][j] = min(dp[i][j], dp[i][j - 1])
    write_i(dp[n - 1][n - 1])
print_ans()

Solution (Python):
def read_int():
    return int(input())

def read_ints():
    return map(int, input().split(' '))
t = read_int()
for case_num in range(t):
    n = read_int()
    cnt = [0 for i in range(26)]
    ps = [[0 for j in range(n + 1)] for i in range(26)]
    pt = [[0 for j in range(n + 1)] for i in range(26)]
    s = input()
    t = input()
    for i in range(n):
        ch = ord(s[i]) - ord('a')
        cnt[ch] += 1
        for j in range(26):
            ps[j][i + 1] = ps[j][i] + (1 if ch == j else 0)
    for i in range(n):
        ch = ord(t[i]) - ord('a')
        cnt[ch] -= 1
        for j in range(26):
            pt[j][i + 1] = pt[j][i] + (1 if ch == j else 0)
    ok = True
    for i in cnt:
        if i != 0:
            ok = False
            break
    if not ok:
        print(-1)
    else:
        r = n
        while r >= 1 and s[r - 1] == t[r - 1]:
            r -= 1
        inf = int(100000000.0)
        dp = [[0 if i == 0 else inf for j in range(r + 1)] for i in range(r + 1)]
        for i in range(1, r + 1):
            for j in range(i, r + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
                ch = ord(t[j - 1]) - ord('a')
                if ps[ch][r] - ps[ch][i] > pt[ch][r] - pt[ch][j]:
                    dp[i][j] = min(dp[i][j], dp[i][j - 1])
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
        print(dp[r][r])

Solution (Python):
INF = float('inf')

def solve():
    N = int(input())
    A = input().strip()
    B = input().strip()
    Acount = [[0] * 26 for _ in range(N + 1)]
    Bcount = [[0] * 26 for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        Acount[i][ord(A[i]) - ord('a')] += 1
        Bcount[i][ord(B[i]) - ord('a')] += 1
        for j in range(26):
            Acount[i][j] += Acount[i + 1][j]
            Bcount[i][j] += Bcount[i + 1][j]
    for i in range(26):
        if Acount[0][i] != Bcount[0][i]:
            return -1
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    for j in range(N + 1):
        dp[0][j] = 0
    for i in range(1, N + 1):
        s = ord(A[i - 1]) - ord('a')
        for j in range(i, N + 1):
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
            t = ord(B[j - 1]) - ord('a')
            if Acount[i][t] > Bcount[j][t]:
                dp[i][j] = min(dp[i][j], dp[i][j - 1])
            if s == t:
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
    return dp[N][N]
if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        print(solve())