I have been working my way through the exercises in the book Cracking the Coding Interview. I wanted to get feedback for the following exercise.

Write a method to replace all spaces in a string with '%20'. You may assume that the string has sufficient space at the end to hold the additional characters and that you are given the true length of the string.

Example:

Input: "Mr_John_Smith____ ", 13
Output: "Mr%20John%20Smith"

Note: I am using '_' to represent spaces above because I could not get spaces to format nicely.

I would be interested in feedback on my code and time/space complexity computation below, and would also be interested to know if there is any way to improve the time or space complexity of my code.

def urlify(in_string, in_string_length): in_string = list(in_string) for position, character in reversed(list(enumerate(in_string[0:in_string_length]))): if character == ' ': in_string[position + 3:in_string_length + 2] = in_string[position + 1:in_string_length] in_string[position:position + 3] = '%20' in_string_length += 2 return ''.join(in_string) 

My guess is that the time complexity of the code above is \$O(1(n - s) +sn)\$ where \$n\$ is the length of the input string, \$ s\$ is the number of spaces in the input string (not including trailing spaces).

My reasoning is that if there are 0 spaces then the for loop will only do constant work checking the if statement and then perform the join at the end which all together is \$O(n)\$ whereas in the other extreme case where there are \$n\$ spaces, the work done will be \$O(n^{2})\$. Lastly I think the space complexity is \$O(n).\$