Improving and optimizing squeeze() function I am currently reading The C Programming Language by Dennis Richie and Brian Kernighan, and I came to implement the function squeeze (s1, s2) as an exercise. squeeze() deletes each character in s1 that matches any character in the string s2. While coding squeeze(), I thought that I can extend its capability to act like trim() method in Java, and then the my code was already done, and tested. 

However, even though it is implemented in C, I believe that the code below can be improved and optimized. Please help me do so.

char *squeeze (char *str1, char *str2) {

     int i, j;
     int str1Len = strlen (str1);
     int toBeSubtractLen = 0; 

     char chr1 = '\0';
     char chr2 = '\0';

     for (i = 0; i &lt; str1Len; i++) {
          chr1 = str1 [i];
          for (j = 0; j &lt; strlen (str2); j++) {
               chr2 = str2 [j];
               if (chr1 == chr2) {
                    toBeSubtractLen++;     
               }               
          }
     }

     char *finalStr;
     finalStr = malloc ((str1Len - toBeSubtractLen) + 1);
     if (finalStr == NULL) {
          printf ("Unable to allocate memory.\n");
          exit (EXIT_FAILURE);
     }

     int indx = 0;
     for (i = 0; i &lt; str1Len; i++) {
          chr1 = str1 [i];
          for (j = 0; j &lt; strlen (str2); j++) {
               chr2 = str2 [j];
               if (chr1 == chr2) {
                    break;
               }
          }
          if (chr1 != chr2) {
               finalStr[indx] = chr1;
               indx++;
          }
     }
     return finalStr;

} /* end of squeeze() */


Samples:


str1 = ",AaBbCcDdEeFfGgHhIiJjKkLlMmAaAaAaNnOoPpQqRrSsTtUuVvWwXxYyZz"
str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
str3 = "abcdefghijklmnopqrstuvwxyz"
name = "ChristopherM.Sawi"
birthday = "August14,1988"


Outputs:




1. squeeze-ing str1 by str2 yields: "&lt;space&gt;,&lt;tab&gt;abcdefghijklmaaanopqrstuvwxyz"
2. squeeze-ing str1 by str3 yields: "&lt;space&gt;m&lt;tab&gt;ABCDEFGHIJKLMAAANOPQRSTUVWXYZ"
3. squeeze-ing str2 by str3 yields: "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
4. squeeze-ing name by str3 yields: "C&lt;space&gt;M.&lt;space&gt;S"
5. squeeze-ing birthday by str1 yields: "141988"
You want to avoid repeat iteration over the 2nd string, which is O(N).  Do this N times and you have an O(N2) algorithm.

One trick you could use is to build a lookup table of the chars in str2.  This would cost O(N) and some extra memory upfront, but then subsequent lookups in the table could be brought down to O(1).

Here's a simple example.  The trade-off is this takes a bit more memory and makes some assumptions about the range of char.  It also clobbers the buffer of str1:

#include &lt;limits.h&gt;   // for UCHAR_MAX

char *squeeze (char *str1, char *str2)
{
   char present[UCHAR_MAX + 1] = {0};
   char *src, *dst;

   // Build lookup table of chars in str2
   //
   while (*str2)
      present[(unsigned char)*str2++] = 1;

   // Iterate through str1, removing chars along the way.
   //
   src = dst = str1;
   while (*src)
   {
      // Is *src in str2?
      //
      if (present[(unsigned char)*src])
      {
         // Yes, remove this char.. (Advance src but not dst.)
         //
         ++src;
      }
      else
         *dst++ = *src++;
   }

   // NUL terminator
   //
   *dst = 0;

   return str1;
}