LCPESY-Editorial

PROBLEM LINK:

Practice
Contest

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.

2 Likes

http://www.codechef.com/viewsolution/3432766

Why it got wrong?

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

1 Like

@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

@Ajay K. Verma

aha… thanx

http://www.codechef.com/viewsolution/3405663

my code shows TLE… please help me

according to problem
Both of A and B can contain only alphabet characters (both lower and upper case) and digits.
then why http://www.codechef.com/viewsolution/3785911 is wrong
but
http://www.codechef.com/viewsolution/3785925 is correct.

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

http://www.codechef.com/viewsolution/4178220

Its showing TLE…why???

I got WA.what’s wrong in this??
http://www.codechef.com/viewsolution/7279130

https://www.codechef.com/viewsolution/10633951.Why i am getting wrong answer ? can anybody check?

Why am i getting WA?

Link : - https://www.codechef.com/viewsolution/14644176

link text

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

//