PROBLEM LINK:
Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest
Author: Reyaan Jagnani
Tester: Sarvesh Kesharwani
Editorialist: Sarvesh Kesharwani
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
We are given 2 strings, S and P, of equal length. The task is to find the minimum number of operations required to convert the string P into S. Both the strings consist of lowercase english alphabets and/or a character ?. The character ? can be present in either of the strings, both of them or none of them.
First of all, you are supposed to choose a lowercase english alphabet and replace all the occurrences of character ? with that alphabet. In case ? is present in both the strings, every ? should be assigned the same character. Now, since both the strings consist of only lowercase english alphabets, you can apply the following operations.
In one operation, you can do any one of the following:
- Convert any vowel to any consonant.
- Convert any consonant to any vowel.
Find the minimum number of operations to be performed on the string P to make it equal to the string S.
EXPLANATION:
Suppose we replace every ? with 'a'. Now we will iterate through the strings,
at ith index,
if S_i is vowel and P_i is consonant, in one move we can change P_i from consonant to vowel.
if S_i is consonant and P_i is vowel, in one move we can change P_i from vowel to consonant.
if S_i is consonant and P_i is consonant :
if S_i\neq P_i, in two moves we can make S_i = P_i i.e. change P_i to a vowel, again change it to consonant equal to S_i.
if S_i = P_i, no moves are required as they are already equal.
if S_i is vowel and P_i is vowel,
if S_i\neq P_i, in two moves we can make S_i = P_i i.e. change P_i to a consonant, again change it to vowel equal to S_i.
if S_i = P_i, no moves are required as they are already equal.
After the iteration we will get the number of moves required to change string P to string S.
Similarly, we can replace every alphabet with the '?' and count the number of moves using the above logic.
Output the minimum number of moves calculated by replacing all the alphabets with ’?’.
TIME COMPLEXITY:
O(26*N)
SOLUTION
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
map<char,int> vowel;
vowel['a'] = 1, vowel['e'] = 1, vowel['i'] = 1, vowel['o'] = 1, vowel['u'] = 1;
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string s1,s2;
cin>>s1>>s2;
int ans = n*2;
for(char a1 = 'a'; a1<='z'; a1++)
{
int cnt = 0;
for(int i=0; i<n; i++)
{
char ch1 = s1[i];
char ch2 = s2[i];
if(ch1=='?') ch1 = a1;
if(ch2=='?') ch2 = a1;
if(ch1==ch2) continue;
if((vowel.find(ch1)==vowel.end() && vowel.find(ch2)==vowel.end()) || (vowel.find(ch1)!=vowel.end() && vowel.find(ch2)!=vowel.end()))
{
cnt+=2;
}
else cnt++;
}
ans = min(ans, cnt);
}
cout<<ans<<endl;
}
return 0;
}
Python Solution
vowel={"a","e","i","o","u"}
def solve(N,a1,a2,v):
ans=0
for i in range(N):
a,b=a1[i],a2[i]
if (a=="0"):
a=v
if(b=="0"):
b=v
if (a==b):
continue
else:
flag=0
if (a in vowel):
flag=flag+1
if (b in vowel):
flag=flag+1
if(flag==1):
ans=ans+1
else:
ans=ans+2
return ans
T=int(input())
for _ in range(T):
N=int(input())
s1=list(input())
s2=list(input())
ans=2*N
for a in range(26):
ans=min(ans,solve(N,s1,s2,chr(96+a)))
print(ans)
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
set<char> vowel;
void solve()
{
vowel.insert('a');
vowel.insert('e');
vowel.insert('i');
vowel.insert('o');
vowel.insert('u');
int tc;cin>>tc;while(tc--)
{
long long n;
string s1,s2;
cin>>n>>s1>>s2;
vector<long long> ans(26);
for(int i=0;i<26;i++){
int cnt = 0;
for(int j=0;j<n;j++){
char c1 = s1[j];
char c2 = s2[j];
if(s1[j] == '?')s1[j] = char('a' + i);
if(s2[j] == '?')s2[j] = char('a' + i);
if(s1[j] != s2[j]){
bool ok1 = vowel.find(s1[j]) != vowel.end();
bool ok2 = vowel.find(s2[j]) != vowel.end();
if(ok1^ok2)cnt++;
else cnt+=2;
}
s1[j] = c1;
s2[j] = c2;
}
ans[i] = cnt;
}
cout<<*min_element(ans.begin(),ans.end())<<'\n';
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}