Adding Spaces to a String

Adding Spaces to a String

What is this problem about?

In the Adding Spaces to a String interview question, you are given a string and an array of integers representing indices where spaces should be inserted. For example, if the string is "CodeIsFun" and the indices are [4, 6], the output should be "Code Is Fun". The indices refer to the positions in the original string.

Why is this asked in interviews?

Companies like Microsoft and Bloomberg use this problem to test basic Simulation and string efficiency. In many languages, strings are immutable, so building a string character-by-character can be very slow $(O(N^2))$. This problem checks if you know how to use more efficient structures like string builders or character arrays.

Algorithmic pattern used

This problem uses a Two Pointers interview pattern or a simple Linear Scan. You maintain one pointer for the string characters and another for the spaces array. As you iterate through the string, you check if the current index matches the next value in the spaces array.

Example explanation

Input: s = "LearnToCode", spaces = [5, 7]

1. Iterate through s. At index 0, 1, 2, 3, 4, append characters 'L', 'e', 'a', 'r', 'n'.
2. Index matches spaces[0] (which is 5). Append a space: "Learn ".
3. Append 'T', 'o'.
4. Index matches spaces[1] (which is 7). Append a space: "Learn To ".
5. Append 'C', 'o', 'd', 'e'. Result: "Learn To Code".

Common mistakes candidates make

• Inefficient Concatenation: Using result += s[i] in a loop (in Java or Python), which causes a new string to be created every time.
• Index Confusion: Forgetting that once you add a space, the "new" index of the string changes. It's much easier to use the original indices as the guide.
• OutOfBounds: Not checking if you have already processed all the spaces in the spaces array before the string ends.

Interview preparation tip

Always use a StringBuilder (Java), a list of characters (Python), or pre-allocate a character array of the final size (C++) for string-building problems to ensure $O(N)$ time complexity.