URLify a string using Python 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).\$
Your complexity analyses look correct to me.  I would just say, in short, that this function works in O(n2) time.

Note that this is an awkward exercise to do in Python, or any language in which strings are immutable.  Since you can't perform the substitutions in place, you have to return a copy, which means that the minimum space requirement is O(n).  In that case, you might as well do either:

def urlify(in_string, in_string_length):
    return in_string[:in_string_length].replace(' ', '%20')


… or:

def urlify(in_string, in_string_length):
    return ''.join('%20' if c == ' ' else c for c in in_string[:in_string_length])


… which should also be O(n) space, O(n) time, and much simpler to implement!

That said, if we were to reinterpret the exercise to work on a buffer in place, I think that a better approach would be to make one pass to count the spaces in the input, to figure out the length of the output.  Then, copy characters to construct the result, working backwards from the end.  That algorithm should take O(n) time and O(1) space.

In summary, depending on how you interpret the exercise, the solution should either be simpler or faster than what you wrote.