URLIfy a character array using Python - follow-up

This is a follow up to my last code review:

URLify a string using Python

This problem has been reviewed in other languages, but I tried to solve this without looking at those answers.

I am hoping that I achieved \$O(n)\$ time and \$O(1)\$ space as was explained in my last review. I would also appreciate any tips on improving clarity and/or making the code more pythonic without sacrificing time/space complexity.

def count_spaces(in_char_array):
   num_spaces = sum(1 for char in in_char_array if char == ' ')
   return  num_spaces

def urlify(in_char_array, true_length):
   num_spaces = count_spaces(in_char_array[:true_length])
   urlified_length = true_length + 2*num_spaces

   urlified_pos = urlified_length - 1
   for in_char in reversed(in_char_array[:true_length]):
       if in_char == ' ':
           in_char_array[urlified_pos-2:urlified_pos+1] = '%20'
           urlified_pos -= 3
       else:
           in_char_array[urlified_pos] = in_char
           urlified_pos -= 1
    return in_char_array

I tested this as follows -

urlified_string = urlify(list('Mr John Smith    '), 13)

print(urlified_string)
print(''.join(urlified_string))

The output was:

['M', 'r', '%', '2', '0', 'J', 'o', 'h', 'n', '%', '2', '0', 'S', 'm', 'i', 't', 'h']

Mr%20John%20Smith


\$O(n)\$ time with \$O(1)\$ space is a hard, and somewhat extreme requirement.
Sure the \$O(n)\$ can be achieved easily. But the \$O(1)\$ is not.

Using lists, to achieve \$O(1)\$ means you have to change the list in-place.
This means any slicing or helper methods are instantly not an option.
This was pointed out by 200_success.
Take:

>>> a = 'abc  '
>>> id(a)
51272544
>>> id(a.strip())
48713152
>>> id(a[:-2])
44833440
>>> del a[-2:]
TypeError: 'str' object does not support item deletion
>>> a = list('abc  ')
>>> id(a)
51232040
>>> id(a.strip())
AttributeError: 'list' object has no attribute 'strip'
>>> id(a[:-2])
51246424
>>> del a[-2:]
>>> a
['a', 'b', 'c']
>>> id(a)
51232040

So to achieve the requirements you need is hard.
And I'd say unreasonable in the real world.

I also agree with Phrancis that your functions input is bad.
To achieve what you want, we'd want to manually implement strip.
And we're only allowed to make in place changes to the array.
This means the function will be, using type hints, inplace_strip(data: list).

Since strip removes just spaces at the front and back of the list, it's easy to implement efficiently.
Just count the amount of places to remove from the front and back, and then delete them.

def inplace_strip(data: list):
    for i in range(len(data)):
        if data[i] != ' ':
            break
    else:
        del data[:]
        return None
    if i:
        del data[:i]

    for i in range(len(data)-1, -1, -1):
        if data[i] != ' ':
            break
    if i != len(data):
        del data[i+1:]

Is this still \$O(n)\$ time? Yes.
If we look at the time complexity of the list operations I used, then we should see that they are all \$O(n)\$ or smaller.
And so the function is \$O(n)\$.

After this we need to mutate the list so that we can change all ' ' to '%20'.
There are three ways we can do this:

• Set Item, changes the return to ['a', 'b', '%20', 'c'].

• Set Slice, has the time complexity of \$O(k+n)\$.

• Generator, you're going to change the space complexity outside of this function to \$O(n)\$.

So it's really a hard choice.

I'd use a generator as the function 'has no problems', it's you who's changing the space complexity to \$O(n)\$.
And so when ever you get a ' ' you'll yield the '%20'.
But you'll split it up so that there's three yields.

This makes the function simply:

def urlify(data: list):
    inplace_strip(data)
    for char in data:
        if char == ' ':
            yield '%'
            yield '2'
            yield '0'
        else:
            yield char

A function which will always have the usage as, ''.join(urlify(data)).
And so wastes all that hard work.
Instead I'd say to use str.strip and str.translate, this makes the code much simpler, which allows you to change the function to:

def urlify(data: list):
    return data.strip().translate({ord(' '): '%20'})

StackExchange Code Review Q#141391, answer score: 5