Given a char array with words in it, find all 'a' characters and replace with xyz. Modify the input array, do not create a copy of the array

This is an interview question. I wanted to know if instead of 'a' we 开发者_运维知识库want to replace 'xyz' does that mean we have to create 2 extra space or can I increase the size at that particular index? What could be the most efficient complexity of it in terms of running time.

Thanks!

To do this efficiently, you want to scan forwards through the string counting the 'a's, then scan backwards copying the characters directly to their correct final position while injecting 'xyz's as necessary:

• move a pointer through the string from the start until you find the end
  • as it moves, count the number of 'a's
• while the a_count is not 0, move the pointer backwards through the string
  • if the pointer isn't on an 'a', copy the character under the pointer to an address a_count * 2 characters forwards of the pointer
  • else (you're pointer is to an 'a'), copy 'xyz' to address pointer + --a_count * 2

This approach is O(N) where N is the number of characters in the string.

Complexity will be O(strlen(in)), optimization is going to be focused on the constant.

I've come up with a simple, relatively efficient implementation. Note that since we are told to build the result in-place, we MUST assume that the original buffer is large enough to accommodate the growth.

Going to test it on ideone.

Done: http://ideone.com/nAgej

This is quite simple. Just needs 2 passes and is O(n).

1. Count # of 'a' in string
2. Using length of original string and # of 'a', compute the limits of the modified string
3. Do a reverse pass on the string and replace 'a' by 'xyz'

Here is a C implementation of this. Note that I have made the replaceable string a variable in replace you can change it to anything else of any length, just make sure that the array has enough space.

#include <stdio.h>
#include <string.h>

int main() {
    char arr[1024];
    char search='a', *replace="xyz";

    fgets(arr,1023/strlen(replace),stdin);
    if (arr[strlen(arr)-1]=='\n')
        arr[strlen(arr)-1]='\0';
    puts(arr);

    int i, j, k, offset, target;
    for (i=offset=0; i<strlen(arr); ++i)
        if (arr[i]==search)
            offset+=strlen(replace)-1;

    target = strlen(arr)+offset;
    for (i=strlen(arr); i>=0; --i) {
        if (arr[i]!=search)
            arr[target--] = arr[i];
        else {
            target -= strlen(replace);
            strncpy(&arr[target+1],replace,strlen(replace));
        }
    }

    puts(arr);

    return 0;
}