Replace And Remove "straightforward" implementation

#1

Hi, In version 1.5.7, problem 7.4 (REPLACE AND REMOVE), the introduction said there is a very straightforward implementation if the function can allocate O(n) extra space, where n is the size of the input string.

Shouldn’t that read O(2n) extra space? If you can only allocate O(n) extra space and the input string is completely full of ‘a’ characters, you are still going to have to play tricks with writing backwards and in-place etc.

On the other hand if you can allocate O(2n) extra space you can just zoom through in one pass copying (or not) the proper characters to the output string.

Am I understanding this correctly? The problem solution also says it is trivial if we can write to a new string, but it doesn’t elaborate on the size of that new string.

Thanks!

0 Likes
#2

Hey Nick,

I think you are mostly right. The maximum extra space you required is exactly 2n, in the case where all characters are ‘a’. In terms of space complexity, it is O(n). About how to solve problem if you have 2n space, it is just simple going through the original string and simulate based on the character you encounter.

0 Likes