You can first scan the array in the forward direction and find out how many replaces there will be and which ones. After that, you can go back performing all the replaces in O(n). Thus, each char will be moved no more than once.