PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: bernarb01
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic programming
PROBLEM:
You’re given two strings S and T.
You can perform the following operation on string S:
- Choose a non-empty substring, and replace it with its first character.
Find the minimum number of moves required to make S equal to T.
EXPLANATION:
From solving the easier version, recall that our operation is equivalent to deleting a substring of S that is not a prefix.
This time though, we can only apply it to S.
We use dynamic programming, in a similar spirit to the longest common subsequence problem.
Let \text{dp}[i][j] denote the minimum number of deletion operations needed on the first i characters of S, so that the result is the first j characters of T.
Looking at S_i, we have two options.
First, if S_i = T_j, we can consider not deleting S_i.
Then, the first j-1 characters of T should come from the first i-1 characters of S, and the minimum cost of doing that is simply \text{dp}[i-1][j-1].
Second, we can consider deleting S_i - or more precisely, some substring ending at index i.
If we fix the substring S[k\ldots i] to be deleted, the optimal solution from the remaining part is \text{dp}[k-1][j], since we still need to make the first j characters of T from the remaining characters of S.
So, trying all k \leq i, we obtain
This, just by itself, is too slow: there are N\cdot M states in the DP, and each of them has \mathcal{O}(N) transitions by iterating across all k.
To optimize the transitions, let’s store \text{best}[i][j] to be the minimum value of \text{dp}[k][j] across all k \leq i.
In other words, \text{best}[i][j] represents the prefix minimum of the \text{dp} table, taken across each column.
This immediately speeds up the transitions for \text{dp}, since we can now simply take 1 + \text{best}[i-1][j] rather than having to iterate over all k \leq i.
Of course, transitions for \text{best} are themselves trivial: \text{best}[i][j] = \min(\text{dp}[i][j], \text{best}[i-1][j]).
This way, we’re down to \mathcal{O}(N\cdot M) states with \mathcal{O}(1) transitions from each, which is fast enough.
Make sure to set the base cases for the DP correctly, since the first character of S cannot be deleted.
TIME COMPLEXITY:
\mathcal{O}(N \cdot M) per testcase.
CODE:
Author's code (C++)
/**
* author: BERNARD B.01
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef B01
#include "deb.h"
#else
#define deb(...)
#endif
const int N = 2003;
const int inf = int(1e9) + 9;
int n, m;
string s, t;
int dp[N][N][2];
int sol(int i, int j, int k) {
if (i == n) {
return (j == m ? 0 : inf);
}
int& ret = dp[i][j][k];
if (ret != -1) {
return ret;
}
ret = inf;
if (j < m && s[i] == t[j]) {
ret = min(ret, sol(i + 1, j + 1, 0));
}
ret = min(ret, 1 - k + sol(i + 1, j, 1));
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
cin >> n >> m;
cin >> s >> t;
if (s[0] != t[0]) {
cout << -1 << '\n';
continue;
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j][0] = dp[i][j][1] = -1;
}
}
int ans = sol(0, 0, 0);
if (ans >= inf) {
cout << -1 << '\n';
} else {
cout << ans << '\n';
}
}
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, m = map(int, input().split())
a = input().strip()
b = input().strip()
# dp[i][j] -> min moves to make on i chars of a to make it equal to first j chars of b
# delete a[i] -> 1 + min(dp[x][j]) for x < i
# if a[i] = b[j], option 2: don't delete a[i] -> dp[i-1][j-1]
dp = [10**9]*(m+1)
best = [10**9]*(m+1)
dp[0] = best[0] = 0
for c in a:
for j in reversed(range(m)):
dp[j+1] = 1 + best[j+1]
if b[j] == c: dp[j+1] = min(dp[j+1], dp[j])
best[j+1] = min(best[j+1], dp[j+1])
dp[0] = 10**9
if dp[m] >= 10**8: print(-1)
else: print(dp[m])