Interview Question for Software Engineer at Microsoft:

//C/C++ samples
//Replaces every char c with sub-string "XYZ"
//Allocates memory for the new string on the heap - use delete [] if needed.
char* swap_sub_str ( char* input_string, char c, char *sub_str )
{
     //do error checking here

    //count occurrences of the c character in the input string
    unsigned int count = 0;
    for (unsigned int i = 0; i < strlen(input_string); i++)
    {
         if (input_string[i] == c) count++;
    }

    if ( count == 0) return NULL; //nothing to do;

    //allocate new string
    unsigned int new_size = strlen(input_string) + count * strlen(sub_str);
    char * new_string = new char[new_size + 1]; //account for '/0'

    //construct the new string, replacing every occurrence of 'c' with substring
    char* k = new_string ;
    for (unsigned int i = 0; i < strlen(input_string); i++)
    {
         if (input_string[i] != c)
         {
               *k = input_string[i];
                k++;
         }
          else
         {
              memcpy( k, sub_str, strlen(sub_str)); //don't include '/0' into memcopy
              k += strlen(sub_str); //move the pointer
         }
    }
    *k = '\0'; // add zero-terminator

    return new_string ;
}