Could someone tell me if there's a better way of doing this? I was asked this question in an interview and I wrote a piece of code of O(n2).

// This function returns a new string of the common alphabets found in a and b
char* intersection(char*a, char* b)
   static char temp[20];
   int i = 0;
   if ( (a==NULL) || (b==NULL))
         while ( a != NULL)
               if(strchr(b, *a))
                    temp[i] = *a;

    return temp;


If the two strings are not sorted, the 'best' way depends on what trade off you want to make. If you want to have a small memory footprint but slower algorithm your way is fine. If you want to have a faster algorithm at the cost of more memory, two histogram tables is a good way:

define sa as array[0..CHAR_MAX] = {0}
define sb as array[0..CHAR_MAX] = {0}

// build the histograms
for x = 0 to a.length

for x = 0 to b.length

// print the unique intersection
for x = 0 to CHAR_MAX
    if sa[x] <> 0 and sb[x] <> 0 then
        print x as char
    end if

In C that comes out to about a 10 line function and it has O(n) time complexity.

Yes, I agree. Your code takes more memory and runs faster. I still need to figure out if there are other options. I'll give it another try.

Thanks a lot.


I still need to figure out if there are other options.

There are other options, but not for two unsorted strings. Most intersection algorithms assume that both sets are sorted and use an algorithm that is both fast and uses little or no extra memory.

Thanks Tom. I'll read about those algorithms.