PROBLEM LINK:
Author: Roman Furko
Testers: Pushkar Mishra and Sergey Kulik
Editorialist: Pawel Kacprzak
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng
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:

If only one string contains a
question mark on the ith position.Without loss of the generality,
let’s assume that S1[i] = ‘?’ and
S2[i] = ‘a’. Since the latin
alphabet has 26 letters, we can
produce a mismatch by setting up
S1[i] to any letter different by ‘a’
and we can produce a match by
setting up S1[i] to ‘a’. 
Both strings contain a question mark
on the ith positionSince the latin alphabet has 26
letters, we can produce a match by
setting up S1[i] = S2[i] = ‘a’ and
we can produce a mismatch by setting
up S1[i] = ‘a’ and S2[i] = ‘b’.
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.