Header Ads Widget

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 such that  is a vowel, and change  to any consonant.
  • Pick an index 1 such that  is a consonant, and change  to any vowel.

Note: The vowels are the 5 characters {,,,,} — 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

  • 1104
  • 1105
  • The sum of all  across all test cases does not exceed 5105.
  • =
  • 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;
//Rushikesh Taskar

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()
{
//Rushikesh Taskar
ios::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
cin.tie(nullptr);
    int tc=1;
    cin>>tc;
    while(tc--)
    {
     solution();
    
    }
    return 0;
}

Code(JAVA):-
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
//cases
//1. both vowels =+2
//2. both consonents = +2
//3. both ? = nothing
//4 one vowel one consonent =+1
// we also maintain count of ?-vowels and ?-consonents whichever is greater
// cases 2
//?-vowels count == ?-consonents so we simply add
    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        
        Scanner sc = new Scanner(System.in);
        
        int T= sc.nextInt();
        while(T-->0){
         int n = sc.nextInt();
         String s = sc.next();
         String p = sc.next();
         int res =Integer.MAX_VALUE;
         for(int i=0;i<26;i++){
         char[] s1 = s.toCharArray();
         char[] p1 = p.toCharArray();
         int cur = 0;
         for(int j=0;j<n;j++){
         if(s1[j]=='?'){
         s1[j] = (char)(i+97);
         }
         if(p1[j]=='?'){
         p1[j] = (char)(i+97);
         }
         if(s1[j]==p1[j]){
         continue;
         }
         // System.out.println(s1[j]+" "+p1[j]+" "+cur+" "+(char)(i+97));
         if(isVowel(s1[j])&&!isVowel(p1[j])){
         cur+=1;
         }else if(!isVowel(s1[j])&&isVowel(p1[j])){
         cur+=1;
         }else if(isVowel(s1[j])&&isVowel(p1[j])){
         cur+=2;
         }else if(!isVowel(s1[j])&&!isVowel(p1[j])){
         cur+=2;
         }
         }
         // System.out.println(cur+" "+(char)(i+97));
         res = Integer.min(res,cur);
         }
         System.out.println(res);
        
        }
    }
    
    
    public static boolean isVowel(char ch){
    
    
     if(ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u'){
     return true;
     }
     return false;
    }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-