%20fy the string

Given a string¹, replace all spaces with %20. Assume that the string has sufficient space at the end to hold additional characters. Also, the “true” length of the string is given. Make sure the space occupied is constant.

Example

1
2
Input:  "Mr John Smith    ", 13
Output: "Mr%20John%20Smith"

Solution

Complexity: $T = O(n), S = O(1)$

Because the question says that we have some buffer in the end of the string, and we are given the “true” length of the string, we can start from the end, and move every character from the “true” end to the string end. If we encounter a space, we place a %20 instead

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def percent_twentyfy(st, n):
  assert type(st) == bytearray # `isinstance` would be better
  idx = len(st) - 1 # The end of the string
  jdx = n-1 # The "true" end of the string
  while idx >= 0 and jdx >= 0:
    if st[jdx] == ord(' '):
      st[idx] = '0'
      st[idx-1] = '2'
      st[idx-2] = '%'
      idx -= 3
    else:
      st[idx] = st[jdx]
      idx -= 1
    jdx -= 1

This is a test test