nomorequestions nomorequestions - 1 month ago 8
C Question

Finding common characters in two strings

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

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.