PROBLEM LINK:
Author: Shiplu
Tester: Hiroto Sekido, Gerald Agapov
Editorialist: Ajay K. Verma
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Ad-hoc
PROBLEM:
Given two alphanumeric strings, find the number characters which occur in both of them.
QUICK EXPLANATION:
For each string find the multiset of characters present in the string. The answer is the number of common elements in the two multisets. Since there are only 62 (26 + 26 + 10) possible characters, the multiset of characters present in a string can be represented by an integer array of size 62.
EXPLANATION:
Since we are interested in the number of common characters present in both strings, the order in which they appear in the two strings is irrelevant. For each string one needs to find the multiset of characters which appear in it. The intersection of the two multisets will be the longest pattern. Note that in a multiset the same character may appear more than once.
Since there are only 256 possible characters, we can represent the multiset of characters present in a string by an integer array charSet of size 256, where charSet[i] represents how many times character i appear in the string. The code below computes such array for a string. Note that, even though in this problem the characters are limited to Latin alphabets and digits, for the sake of simplicity, we ignore this restriction and assume that any character can occur in the strings.
// Takes a string s, and computes the multiset of characters in it.
// The multiset is represented by the integer array charSet.
void computeSet(const string& s, int* charSet) {
for (auto c : s) {
++charSet[c];
}
}
After we have computed the integer arrays for two strings, the number of common characters can be computed by iterating though all possible characters and checking how many occurrences of this character are common between the two strings.
count = 0;
for (int i = 0; i < 256; ++i)
count += min(charSet1[i], charSet2[i]);
TIME COMPLEXITY:
O (m + n),
where m and n are the lengths of the strings.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be put up soon.
Tester’s solution will be put up soon.
-