PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: bernarb01
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
simple
PREREQUISITES:
None
PROBLEM:
You’re given two strings S and T.
You can perform the following operation on either string:
- 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:
Observe that the given operation is essentially “choose a substring, and delete all its characters other than the first”.
So, we can delete any substring of either S or T, with one exception: we cannot delete a prefix (since to delete a substring, there must be a character before it in order for the operation to be performed).
In particular, neither S_1 nor T_1 can be changed no matter what, so if S_1 \neq T_1 it’s definitely impossible to make S and T equal.
Now, suppose S_1 = T_1.
Note that it’s always possible to make S and T equal using at most 2 moves:
- Choose the entire string S, which will delete every character of S except S_1.
- Choose the entire string T, which will delete every character of T except T_1.
S and T now both equal the single character S_1.
So, the number of moves required is \leq 2.
We now need to find out whether 0 or 1 moves will be enough.
Checking for 0 moves is trivial: S and T should be already equal.
Let’s now analyze when 1 move is enough.
Suppose we delete the substring [L, R] of S, and it becomes equal to T.
Then,
- R-L+1 should equal N-M, i.e, the length of the deleted substring should equal the difference in lengths between S and T.
- The prefix of length L-1 of S must equal the prefix of length L-1 of T.
- The suffix of length M-(L-1) of S must equal the suffix of length M-(L-1) of T.
Note that the suffix of length M-(L-1) of S is simply every character after index R.
So, what really matters is how long the prefixes and suffixes of S match the corresponding ones in T.
There are now several ways to perform the required check quickly:
- You can compute boolean arrays \text{pref} and \text{suf}, where \text{pref}_i is true if and only if the length i prefixes of S and T are equal; \text{suf} is defined similarly for the suffix.
Then, iterate over every substring of length N-M in S, and use the precomputed arrays to check whether the necessary condition holds in \mathcal{O}(1).
Similarly, iterate over every substring of length M-N in T and do the same check.
This is \mathcal{O}(N), since there are \leq N substrings of a fixed length (at most one for each starting position). - Even simpler, let x and y denote the lengths of the longest prefix match and suffix match between S and T.
Then, a valid operation exists if and only if x+y \geq \min(N, M).
The checks for whether the answer is 0 or 1 can be performed in linear time; if they both fail, the answer is 2.
TIME COMPLEXITY:
\mathcal{O}(N + 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
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n, m;
cin >> n >> m;
string s, t;
cin >> s >> t;
if (s == t) {
cout << 0 << '\n';
continue;
}
if (s[0] != t[0]) {
cout << -1 << '\n';
continue;
}
if (n < m) {
swap(n, m);
swap(s, t);
}
int p = 0;
while (p < m && s[p] == t[p]) {
p += 1;
}
int ss = n, st = m;
while (st > p && s[ss - 1] == t[st - 1]) {
ss -= 1;
st -= 1;
}
if (p >= st) {
cout << 1 << '\n';
continue;
}
cout << 2 << '\n';
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n, m;
cin>>n>>m;
string s, t;
cin>>s;
cin>>t;
if(s[0] != t[0]){
cout<<-1<<"\n";
}else{
if(s == t){
cout<<0<<"\n";
}else{
int a = 0;
for(int i = 0; i < min(n, m); i++){
if(s[i] == t[i]){
a++;
}else{
break;
}
}
int b = 0;
for(int i = 0; i < min(n, m); i++){
if(s[n - i - 1] == t[m - i - 1]){
b++;
}else{
break;
}
}
if(a + b >= min(n, m)){
cout<<1<<"\n";
}else{
cout<<2<<"\n";
}
}
}
}
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, m = map(int, input().split())
a = input().strip()
b = input().strip()
if a[0] != b[0]: print(-1)
else:
# ans <= 2
# check 0 and 1
# 0 -> strings already equal
# 1 -> s can be obtained by deleting one substring of t or vice versa; match prefixes and suffixes
if a == b: print(0)
else:
pref, suf = 0, 0
for i in range(min(n, m)):
if a[i] != b[i]: break
pref += 1
for i in range(min(n, m)):
if a[-1-i] != b[-1-i]: break
suf += 1
if pref + suf >= min(n, m): print(1)
else: print(2)