Ti do uno spunto: alloca la stringa di output come preferisci, e usa due puntatori, uno per la lettura dalla stringa originale e uno per la scrittura dalla stringa di destinazione (è un metodo estremamente utilizzato quando si effettuano sostituzioni sulle stringhe). Quando nel ciclo incontrerai una stringa da sostituire (individuabile con la funzione strncmp) potrai copiare direttamente nella stringa di destinazione la stringa sostitutiva (strcpy), spostando avanti (di un numero di caratteri differente, ovviamente) i due puntatori in modo che passino oltre la stringa da sostituire (nel caso del puntatore in lettura) e quella sostitutiva (nel caso del puntatore in scrittura). Nel caso di caratteri da copiare "paro paro", invece, ti basterà fare *writePtr=*readPtr.