In string processing, how would you write a method to replace all spaces in a string with '%20' for use in URLs, without using extra space proportional to the string length?

Introduction / Context:
Replacing spaces with the sequence %20 is a common interview problem that models URL encoding of spaces. It is often stated as: given a character array with sufficient extra buffer at the end, write a method to replace each space in the true string with three characters, percent, two, and zero. The key challenge is to perform the transformation in place, without using extra space proportional to the string length, and to handle overlapping reads and writes correctly.

Given Data / Assumptions:

• The input is a character array or mutable string buffer that contains a string with spaces.
• The buffer has enough extra capacity at the end to hold the additional characters that result from replacements.
• The true length of the string (excluding trailing buffer) is known.
• Every space character ' ' should be replaced by the three character sequence '%20'.
• The goal is an in place O(n) algorithm without allocating another full sized string.

Concept / Approach:
If you scan from the beginning and try to replace spaces with %20 in place, you will overwrite characters that you have not processed yet, because the replacement is longer than the original single space. To avoid this, the standard trick is to work from the end of the true string toward the beginning. First, you count the number of spaces to determine the final length. Then, you use two indices: one at the original end of the true string and one at the end of the final position. You copy characters from the back. When you see a non space character, you copy it once. When you see a space, you write 0, 2, and % into the buffer at the destination index, moving the destination index three positions left. This guarantees that you never overwrite characters that you still need to read.

Step-by-Step Solution:
Step 1: Count the spaces in the string between index 0 and the last valid character. Let space_count be this value. Step 2: Compute the new length as original_length + 2 * space_count, because each space becomes three characters instead of one. Step 3: Set two pointers: i at original_length - 1 (the last real character) and j at new_length - 1 (the last index in the buffer). Step 4: While i is greater than or equal to 0, check the character at position i. If it is not a space, copy it directly to position j and decrement both i and j by 1. Step 5: If the character at i is a space, write '0' at j, '2' at j - 1, and '%' at j - 2, then decrement i by 1 and j by 3. Continue until i crosses 0, and the buffer now contains the encoded string with spaces replaced by %20.

Verification / Alternative check:
To verify, you can test the method on a sample like 'Mr John Smith' with a buffer that has extra space. Counting spaces gives 2, so the new length is original_length + 4. Running the algorithm from the back correctly produces 'Mr%20John%20Smith'. Because you only pass through the string a constant number of times and each character is moved at most once, the time complexity is O(n). Since you only use a few extra indices and no additional arrays, the space complexity is O(1). As an alternative, you could build a new string using a dynamic builder, but that would use extra space and is not in place.

Why Other Options Are Wrong:
Option B deletes spaces instead of encoding them, changing the content and potentially joining words incorrectly. Option C modifies only the start of the string and leaves internal spaces unchanged, failing to meet the requirement. Option D is arbitrary and incorrect because encoding must be consistent and deterministic. Option E changes letter case but does not address spaces at all, so it is unrelated to URL style encoding.

Common Pitfalls:
A common mistake is to forget to account for the final length and therefore either overwrite characters or write beyond the allocated buffer. Another pitfall is running the algorithm from the front, which leads to overwriting unprocessed characters or requiring extra buffers. Some candidates also mishandle edge cases, such as strings with no spaces, strings that start or end with spaces, or empty strings. Carefully handling indices and always moving from the end to the beginning avoids these issues.

Final Answer:
The correct in place method is to compute the final length, then walk the string from the end toward the start and for each space write '%20' at the destination index while copying other characters directly, using a two index technique so that all spaces are replaced with '%20' without overwriting unread characters.