Header Ads Widget

Marbles | codechef solution

Rajnish Tripathi 10:27

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

  • 1≤�≤104
  • 1≤�≤105
  • The sum of all � across all test cases does not exceed 5∗105.
  • ∣�∣=∣�∣
  • 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:-

Tags:

Post a Comment

0 Comments