Replace and remove

Write a function which takes as input a string s, and removes each "b" and replaces each "a" by "dd". Use 0(1) additional storage-assume s is stored in an array that has enough space for the final result

Solution

• The constraint here is space. The trick is knowing there is extra space at the end of the string to accommodate the result string after computation.
• Start parsing the string from the last char and insert the result chars towards the end of the string.

Code

i = find_last_char(str)
j = str.length -1

while i >= 0
    if str[i] == 'b'
        i -= 1
    elsif str[i] == 'a'
        str[j] = 'd'
        j -= 1
        str[j] = 'd'
        j -= 1
    else
        str[j] = str[i]
        j -= 1
        i -= 1
    end
end

return str

Time complexity

O(n) since we're traversing the string only once