Строить список позиций замены, заодно подсчитывать результирующую длину строки, выделять память один раз, в цикле по списку замен делать Move(Src->Dst)+Move(ReplaceN->Dst).
Заодно и скорость увеличится на бинарных данных с множеством #0 и #1.