PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Lavish Gupta
Tester: Lavish Gupta, Abhinav sharma, Takuki Kurokawa
Editorialist: Devendra Singh
DIFFICULTY:
1092
PREREQUISITES:
None
PROBLEM:
Given a string A of length N consisting of lowercase English alphabet letters.
You are allowed to perform the following operation on the string A any number of times:
- Select a non-empty subsequence S of the array [1,2,3,\ldots,N] and any lowercase English alphabet \alpha;
- Change A_i to \alpha for all i \in S.
Find the minimum number of operations required to convert A into a given string B of length N consisting of lowercase English alphabet letters.
EXPLANATION:
-
Observation 1: No index of the string A will be included in more than 1 operation
Because if it is included in more than 1 operation we can always just remove it from all the operations which include i other than the last operation which includes i and the answer would still be same. -
Observation 2: 2 operations will always have different English characters as alpha.
If we have two operations with same English character as \alpha we can always just merge the subsequences chosen in those two operations and assign all the selected indices with \alpha. -
Observation 3: For each character char from a to z if there exists any index i in string B such that B_i=char and B_i!=A_i exactly one operation has to be done.
If there exists such an index, at least one operation has to be done in which \alpha =char. By observation 2 we have that no more than 1 operation will have same \alpha. It is proved that we need exactly one operation for each such char such that there exists an index i in string B such that B_i=char and B_i!=A_i
From these three observations it is clear that the answer to the problem is number of distinct lowercase English alphabet \alpha such that there exists an index i in string B such that B_i=\alpha and B_i!=A_i.
TIME COMPLEXITY:
O(N) for each test case.
SOLUTION:
Setter's solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll max(ll l, ll r){ if(l > r) return l ; return r;}
ll min(ll l, ll r){ if(l < r) return l ; return r;}
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 10000;
const int MAX_N = 100000;
const int MAX_SUM_N = 100000;
int sum_n = 0 ;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pll pair<ll , ll>
void solve()
{
int n = readIntLn(1 , MAX_N) ;
sum_n += n ;
assert(sum_n <= MAX_SUM_N) ;
string a , b ;
a = readStringLn(n , n) ;
b = readStringLn(n , n) ;
for(int i = 0 ; i < n; i++)
{
assert(((a[i] - 'a') >= 0) && ((a[i] - 'a') <= 25)) ;
assert(((b[i] - 'a') >= 0) && ((b[i] - 'a') <= 25)) ;
}
/*************** Input verified ***************/
set<char> dist_a, dist_b, dist_diff_a, dist_diff_b ;
for(int i = 0 ; i < n ; i++)
{
dist_a.insert(a[i]) ;
dist_b.insert(b[i]) ;
if(a[i] != b[i])
{
dist_diff_a.insert(a[i]) ;
dist_diff_b.insert(b[i]) ;
}
}
cout << dist_diff_b.size() << endl ;
return ;
}
signed main()
{
//fast;
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif
int t = 1;
t = readIntLn(1 , MAX_T) ;
for(int i=1;i<=t;i++)
{
solve() ;
}
assert(getchar() == -1);
// cerr<<"SUCCESS\n";
// cerr<<"Tests : " << t << '\n';
// cerr<<"Sum of lengths : " << sum_n << '\n';
// cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Minimum length : " << min_n << '\n';
// cerr << "Sum o f product : " << sum_nk << '\n' ;
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n, ans = 0;
cin >> n;
string a, b;
cin >> a >> b;
for (int i = 0; i < 26; i++)
{
for (int j = 0; j < n; j++)
if ((b[j] - 'a') == i && a[j] != b[j])
{
ans++;
break;
}
}
cout << ans << '\n';
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}