Cracking the Coding Interview - Replace All Spaces in String

1.4 Write a method to replace all spaces in a string with ‘%20’. You may assume that the string has sufficient space at the end of the string to hold the additonal characters, and that you are given the “true” length of the string

Note: this is part of a series where I expand on solutions in python to questions from the book “Cracking the Coding Interview (5th Edition)” by Gayle Laakman Mcdowell. I’ll be porting over the code provided in the book over to python as well as adding my own solutions and even solutions based on alternative solutions suggested by Gayle. Hope you find it helpful!

This post will cover three solutions:

  • Solution using O(N) space. Don’t mutate the existing array.
  • In-place replacement using existing array.
  • Generalized solution for any character replacement.

Since python strings are immutable, lets assume that our “string” is actually a character list with None values padded at the end to represent the “sufficient space”. Here’s a way of creating character lists using string literals for this problem:

def char_array(string, size):
    output = [None] * size
    for idx, v in enumerate(string):
        output[idx] = v
    return output

Ok lets get to it.

O(N) space solution

Here’s a solution that stores the values in a new list, but doesn’t preserve the original length of the character array.

def replace_spaces(char_array, true_length):
    output = []
    for x in char_array:
        if x == " ":
            output.extend(["%", "2", "0"])
        else:
            output.append(x)
    return output

And then the same solution but with padding at the end to make sure we have the same array length as the original character array.

def replace_spaces(char_array, true_length):
    output = []
    for x in char_array:
        if x == " ":
            output.extend(["%", "2", "0"])
        else:
            output.append(x)
    pad_size = len(char_array) - len(output)
    output.extend([None] * pad_size) 
    return output

Now lets look at the solution from the book (in-place)

In-place modification of existing array (book solution)

This is slightly tricker because we are not doing a one-to-one replacement of a character. If we performs replacements in the array from left to right, we need to shift elements over (starting with the last character) in order to make room for the additional characters.

Here’s an example using repeated shifts everytime we encounter a space (warning: it’s not pretty):

def replace_spaces(char_array, true_length):
    max_shifts = char_array.count(" ")
    size = len(char_array)
    curr_end_idx = true_length - 1
    curr_shifts = 0
    curr_idx = 0
    while curr_idx < size and curr_shifts < max_shifts:
        x = char_array[curr_idx]
        if x == " ":
            # shift right from the end
            for i in range(curr_end_idx, curr_idx - 1, -1):
                char_array[i+2] = char_array[i]
            curr_end_idx += 1
            char_array[curr_idx] = "%"
            char_array[curr_idx + 1] = "2"
            char_array[curr_idx + 2] = "0"
            curr_shifts += 1
            curr_idx += 3
        else:
            curr_idx += 1
    return char_array

This is not optimal because we are shifting the same elements over and over again. How do we avoid that? Well, we can’t avoid shifting elements. However, what if we can shift them into their final location in the array?

If we know ahead of time the number of spaces, then we can figure out exactly how much additional space we need at the end and the final location of the last character in our original string. For example, if we have a single space, then the final true length of the string is going to be 2 more than the original. If we shift the last character by 2, there is guaranteed to be room when we encounter our space character.

Here’s the solution:

def replace_spaces(char_array, true_length):
    num_spaces = char_array.count(" ")
    final_length = true_length + (num_spaces * 2)
    new_char_idx = final_length - 1
    for i in range(true_length - 1, -1, -1):
       c = char_array[i]
       if c == " ":
           char_array[new_char_idx] = "2"
           char_array[new_char_idx - 1] = "0"
           char_array[new_char_idx - 2] = "%"
           new_char_idx -= 3
       else:
           char_array[new_char_idx] = c
           new_char_idx -= 1
    return char_array

As Gayle mentions in the book, this back to front scan is a common approach to performing in-place modifications to character arrays because it side-steps the complexity and inefficiency of doing repeated shifts.

General Solution

Here’s if we generalized the solution for this problem to perform replacement for some variable number of characters (though it doesn’t handle a number of cases such as replacing the space character with an empty string and shortening the array).

def replace_spaces(char_array, true_length, target, replacement_chars):
    num_occurrences = char_array.count(target)
    final_length = (num_occurrences * (len(replacement_chars) - 1)) + true_length
    curr_index = final_length - 1
    for i in range(true_length - 1, -1, -1):
       c = char_array[i]
       if c == target:
           for r_index in range(len(replacement_chars) - 1, -1, -1):
               rchar = replacement_chars[r_index]
               char_array[curr_index] = rchar
               curr_index -= 1
       else:
           char_array[curr_index] = c
           curr_index -= 1
    return char_array

Last thoughts

By the way, if you’re new to python and you actually need to perform string replacement - please don’t do any of the above in production :). The native string .replace is more than sufficient for most cases.

If you’re asked this during an interview and you’re using python, state upfront that you’ll be using a list to represent a character array and why. I wouldn’t assume that your interview knows that strings are immutables in python.