PROBLEM LINK:Author: Roman Furko DIFFICULTY:Cakewalk PREREQUISITES:Implementation PROBLEM:You are given two strings S1, S2 with equal lengths. Both strings, on any position, can contain a lowercase latin letter or a question mark '?'. A question mark can be equal to any of lowercase latin letters. We define the difference between the strings as the number of positions i, such that the strings are different on this position. Your task is to compute the minimal and the maximal difference between the strings. QUICK EXPLANATION:Let's consider any position i in the strings. Since a question mark can be any letter, if at least one of the strings have a question mark on the ith position, we can always change it to match the letter in the other string or we can always change it to a letter which produces a mismatch. Therefore, the minimal difference is the number of positions for which none of the strings contain a question mark and there is a mismatch between them on this position. On the other hand, the maximal difference is the length of the strings reduced by the number of positions for which none of the strings contain a question mark and there is a match between them on this position. EXPLANATION:We define a strong match as the position i, such that none of the strings contain a question mark at the ith position, and the letters in the strings at the ith position match. We define a strong mismatch as the position i, such that none of the strings contain a question mark at the ith position, and the letters in the strings at the ith position do not match. Let's consider any position i in both strings. If at least one string contain a question mark on the ith position, we can create a match or a mismatch between the strings at this position. There are basically two cases to consider:
Based on these two facts, we for any position which is not a strong match or a strong mismatch, we can make it a match or a mismatch. Therefore, the minimal difference is the number of strong mismatches. On the other hand, the maximal difference is the length of the strings reduced by the number of strong matches. Time complexity: Linear in terms of the length of input strings. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 26 Jun '15, 00:13

include <stdio.h>include <string.h>include <math.h>int main() { int t,i,x,y; char s1[102],s2[102]; scanf("%d",&t); while(t) { i=0; x=0; y=0; scanf("%s",&s1); scanf("%s",&s2); while(s1[i]) { if(s1[i]=='?'  s2[i]=='?') x++; else if(s1[i] != s2[i]) y++; i++; } printf("%d %d\n",y,x+y); } return 0; } answered 19 Jan '18, 08:46

include<stdio.h>int main() { int t,minimal,maximal,count,i; char s1[105],s2[105]; scanf("%d",&t); while(t) { scanf("%*c%s%s",s1,s2); i=0; count=minimal=maximal=0; while(s1[i]!='\0') { if(s1[i]=='?'s2[i]=='?') count++; else { if(s1[i]!=s2[i]) minimal++; } i++; } maximal=minimal+count; printf("%d %d\n",minimal,maximal); } return 0; } answered 20 Jan '18, 12:16
