Author: Shiplu
Tester: Hiroto Sekido, Gerald Agapov
Editorialist: Ajay K. Verma






Given two alphanumeric strings, find the number characters which occur in both of them.


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.


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) {

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]);


O (m + n),
where m and n are the lengths of the strings.


Author’s solution will be put up soon.
Tester’s solution will be put up soon.


Why it got wrong?

@Shiplu: By taking boolean array, you are not taking in account the number of times character appears in a string.

For example ,
if first string is ABCA and second string is AACC then you are only accounting A once, rather it should be two, because it appears two times in both strings. Therfore answer for above case will be 3 (Two A’s and one ).

1 Like

according to problem
Both of A and B can contain only alphabet characters (both lower and upper case) and digits.
then why is wrong
but is correct.

because ascii value of A-Z is 65-90
digit 48-57
and a-z 97-122.

I got WA.what’s wrong in this?? i am getting wrong answer ? can anybody check?

Why am i getting WA?

Link : -

link text

for(i=48;i<=125;i++) when initially i is taken as greater than 48 then program is getting WA?

char I[500]; is problem, use two strings with 300x ‘a’ and you will see :wink: -

1 Like

@Ajay K. Verma

aha… thanx

my code shows TLE… please help me

Its showing TLE…why???

Java accepted solution using HashMap:
what is the problem in my solution please check

can any one tell what is wrong with my code it is giving me wrong answer(WA)

consider the test case
answer should be 1(common char is 1)

you will get AC only if you consider digits between 0-9