Finding common characters in two strings

Question

I am coding for the problem in which we got to count the number of common characters in two strings. Main part of the count goes like this

for(i=0; i < strlen(s1); i++) {
    for(j = 0; j < strlen(s2); j++) {
        if(s1[i] == s2[j]) {
            count++;
            s2[j] = '*';
            break;
        }
    }
}

This goes with an O(n^2) logic. However I could not think of a better solution than this. Can anyone help me in coding with an O(n) logic.

Answer 1

This is very simple. Take two int arrays freq1 and freq2. Initialize all its elements to 0. Then read your strings and store the frequencies of the characters to these arrays. After that compare the arrays freq1 and freq2 to find the common characters.

Answer 2

It can be done in O(n) time with constant space.

The pseudo code goes like this :

int map1[26], map2[26];
int common_chars = 0;

for c1 in string1:
    map1[c1]++;

for c2 in string2:
    map2[c2]++;

for i in 1 to 26:
    common_chars += min(map1[i], map2[i]);