Three Strings
Contest: Codeforces Round 991 (Div. 3)
Difficulty rating: 1500
Tags: dp, implementation, strings

You are given three strings: $$$a$$$, $$$b$$$, and $$$c$$$, consisting of lowercase Latin letters. The string $$$c$$$ was obtained in the following way:

1. At each step, either string $$$a$$$ or string $$$b$$$ was randomly chosen, and the first character of the chosen string was removed from it and appended to the end of string $$$c$$$, until one of the strings ran out. After that, the remaining characters of the non-empty string were added to the end of $$$c$$$.
2. Then, a certain number of characters in string $$$c$$$ were randomly changed.

For example, from the strings $$$a=\color{red}{\text{abra}}$$$ and $$$b=\color{blue}{\text{cada}}$$$, without character replacements, the strings $$$\color{blue}{\text{ca}}\color{red}{\text{ab}}\color{blue}{\text{d}}\color{red}{\text{ra}}\color{blue}{\text{a}}$$$, $$$\color{red}{\text{abra}}\color{blue}{\text{cada}}$$$, $$$\color{red}{\text{a}}\color{blue}{\text{cada}}\color{red}{\text{bra}}$$$ could be obtained.

Find the minimum number of characters that could have been changed in string $$$c$$$.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.

The first line of each test case contains one string of lowercase Latin letters $$$a$$$ ($$$1 \leq |a| \leq 10^3$$$) — the first string, where $$$|a|$$$ denotes the length of string $$$a$$$.

The second line of each test case contains one string of lowercase Latin letters $$$b$$$ ($$$1 \leq |b| \leq 10^3$$$) — the second string, where $$$|b|$$$ denotes the length of string $$$b$$$.

The third line of each test case contains one string of lowercase Latin letters $$$c$$$ ($$$|c| = |a| + |b|$$$) — the third string.

It is guaranteed that the sum of $$$|a|$$$ across all test cases does not exceed $$$2 \cdot 10^3$$$. Also, the sum of $$$|b|$$$ across all test cases does not exceed $$$2 \cdot 10^3$$$.

Output format:
For each test case, output a single integer — the minimum number of characters that could have been changed in string $$$c$$$.

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

Example input:
7
a
b
cb
ab
cd
acbd
ab
ba
aabb
xxx
yyy
xyxyxy
a
bcd
decf
codes
horse
codeforces
egg
annie
egaegaeg

Example output:
1
0
2
0
3
2
3

Editorial:
Let's use the idea of dynamic programming. Let $$$dp[i][j]$$$ be the answer to the problem when considering string $$$a$$$ as its own prefix of length $$$i$$$, string $$$b$$$ as its own prefix of length $$$j$$$, and string $$$c$$$ as its own prefix of length $$$i+j$$$.
Then the dynamic programming recurrence is easy: we need to iterate over where we took the next (($$$i+j$$$)-th) character of string $$$c$$$.
If the character is taken from string $$$a$$$, the answer is:
• $$$dp[i - 1][j]$$$, if $$$a_i = c_{i+j}$$$,
• $$$dp[i - 1][j] + 1$$$ otherwise (since we need to replace character $$$a_i$$$ with $$$c_{i+j}$$$).
If it is taken from string $$$b$$$, the answer is calculated similarly:
• $$$dp[i][j - 1]$$$, if $$$b_j = c_{i+j}$$$,
• $$$dp[i][j - 1] + 1$$$ otherwise.
Thus, to obtain the minimum value of the current dynamic programming state, we need to take the minimum of the two obtained values.
To get the answer, we need to take the value of the dynamic programming table at $$$dp[n][m]$$$, where $$$n$$$ is the length of string $$$a$$$ and $$$m$$$ is the length of string $$$b$$$.
The final time complexity of the solution is $$$\mathcal{O}(n \cdot m)$$$ per test case.