# Marbles | codechef solution

## Problem

"You have a reason to leave this place, but I don't."

In the fourth game, Sang-Woo and Ali are competing against each other. Sang-Woo is the more intelligent one between them, and he plans to win the game by cheating. Ali is your childhood friend and you want to help him win this game. The game goes as follows.

Both of them are given $2$ strings — $�$ and $�$ — of equal length (say $�$). The task is to find the minimum number of operations required to convert the string $�$ into $�$. Every character of both $�$ and $�$ is either a lowercase English alphabet or $?$.

First, before performing any operation, you must choose a single lowercase character from the English alphabet, and replace every occurrence of $?$ with this character. Note that every $?$ present in either $�$ or $�$ is replaced by the exact same character. This does not count as an operation.

Once the above step is done, you are allowed to perform the following two operations on $�$ any number of times:

• Pick an index $1\le �\le �$ such that ${�}_{�}$ is a vowel, and change ${�}_{�}$ to any consonant.
• Pick an index $1\le �\le �$ such that ${�}_{�}$ is a consonant, and change ${�}_{�}$ to any vowel.

Note: The vowels are the $5$ characters $\left\{�,�,�,�,�\right\}$ — the other $21$ are consonants.

Find the minimum number of operations required to convert $�$ into $�$.

### Input Format

• The first line of input contains a single integer $�$, denoting the number of test cases. The description of $�$ test cases follows.
• The first line of each test case contains an integer $�$, denoting the length of strings $�$ and $�$.
• The second and third lines contain strings $�$ and $�$ respectively.

### Output Format

For each test case, output in a single line the minimum number of operations required to convert $�$ into $�$.

### Constraints

• $1\le �\le 1{0}^{4}$
• $1\le �\le 1{0}^{5}$
• The sum of all $�$ across all test cases does not exceed $5\ast 1{0}^{5}$.
• $\mathrm{\mid }�\mathrm{\mid }=\mathrm{\mid }�\mathrm{\mid }$
• Every character of both $�$ and $�$ is either a lowercase English alphabet or $?$.
• Every $?$ present in $�$ and $�$ should be assigned the same character.

### Sample 1:

Input
Output
3
5
ab?c?
aeg?k
6
abcde?
ehio??
4
abcd
abcd
4
6
0

### Explanation:

Test Case 1: First, replace every $?$ by $�$. This gives us $�=�����$ and $�=�����$. Now $�$ can be converted to $�$ as follows:

1. Convert ${�}_{2}=�$ to $�$ in 1 operation.
2. Convert ${�}_{3}=�$ to $�$ in 1 operation.
3. Convert ${�}_{4}=�$ to $�$ in 1 operation.
4. Convert ${�}_{5}=�$ to $�$ in 1 operation.

Test Case 3: The strings are already equal, so no operations are required.

Code(C++):-

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

int mod = 1e9+7;

bool check(char ch)
{
if(ch=='a' or ch=='e' or ch=='i' or ch=='o' or ch=='u')
{
return true;
}
return false;
}
void solution()
{
// check with each and every char
// if both are of same category then result 2 operation else 1
int n;
cin>>n;
string s,p;
cin>>s>>p;
int ans=INT_MAX;
for(char ch ='a';ch<='z';ch++)
{
int cur=0;
string ss=s;
string pp=p;
for(int i=0;i<n;i++)
{
if(ss[i]=='?')
{
ss[i]=ch;
}
if(pp[i]=='?')
{
pp[i]=ch;
}
if(ss[i]!=pp[i] and check(ss[i]) == check(pp[i]))
{
cur=cur+2;
}
else if(ss[i]!=pp[i] and check(ss[i])!=check(pp[i]))
{
cur++;
}
}
ans=min(cur,ans);
}
cout<<ans<<endl;
return;
}
int32_t main()
{
ios::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
cin.tie(nullptr);
int tc=1;
cin>>tc;
while(tc--)
{
solution();

}
return 0;
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-