replace single char by 2 chars

[tubby123]

Hey, is there a way to replace a single characters by 2 characters in a string ????
This was asked to me at 1 of the interviews.

I answered linked list, I mean, take each node as a character, so u can easily insert 2 nodes, if u want to replace 2 characters.

Is there a better algo ???

[Narue]

is there a way to replace a single characters by 2 characters in a string ????

Yes, of course.

I answered linked list, I mean, take each node as a character, so u can easily insert 2 nodes, if u want to replace 2 characters.

That's a very inefficient representation of a string, and your idea wouldn't work for array based strings.

[TrustyTony]

It is of course heavy operation, but I think that would basically mean producing new string with two letters added instead of one letter for replacement. In this case, for my opinion, clearest is to use copy anyway. You could copy whole string segment in one memcopy type operation by doing copy only when next occurance is found or end of string is reached. Maybe worthwhile to consider the case that letter to replace was not found, in which case you can just return the original.

[tubby123]

Yes, of course.
That's a very inefficient representation of a string, and your idea wouldn't work for array based strings.

Ma'am, can i know the algorithm or pseudo code.

[Narue]

If the replacement string is larger than the search string:

1. Make room for the extra characters
2. Shift all characters from the insertion point to the end of the string to make a hole
3. Fill in the hole with the replacement string

# Replace 3 with 99
[1][2][3][4][5]    # Original
[1][2][3][4][5][]  # Step 1
[1][2][3][4][4][5] # Step 2
[1][2][9][9][4][5] # Step 3

If the replacement string is shorter than the search string:

1. Fill in the extra space by shifting all characters from the end of the search string to the end of the string over part of the search string
2. Replace what's left of the search string with the replacement string
3. Decrease the size of the string

# Replace 23 with 9
[1][2][3][4][5] # Original
[1][2][4][5][5] # Step 1
[1][9][4][5][5] # Step 2
[1][9][4][5]    # Step 3

If the replacement string is equal in length to the search string:

1. Overwrite the search string with the replacement string