Question: Given an array, remove all the 'a's and add one 'd' after each 'b', do it in O(n)

Solution: Step 1: loop from 0 to n-1; remove all the 'a's, and squeeze the array to the left (starting at index 0) without any spaces in the array (introduced by removing 'a's) other than the end of the array. At the same time, count the number of 'b's: n_b, the index of the new end of the array: m.

Step 2: loop from n_b+m to 0: assign each one with the wanted value by moving at index m or less (or adding a 'd') to the position of index == n_b+m or less.

int i=0, pos = 0, nb = 0, ;
for(int i=0; i if(a[i] == 'b') {
nb++;
}
if(a[i] != 'a') {
a[pos] = a[i];
pos++;
}
}
if(nb==0) return;
// if(nb+pos >= n) should extend the memory of the array first
// (may need to generate a new array)
i = pos;
pos = pos+nb;
for(; i>=0; pos--,i--) {
if(a[i]=='b') {
a[pos] = 'd';
pos--;
a[pos] = 'b';
} else {
a[pos] = a[i];
}
}