Problem Description

You are given a string s (0-indexed) and an integer array spaces (also 0-indexed) that contains indices where you need to insert spaces into the original string. Each space should be inserted before the character at the specified index.

For example:

• Input: s = "EnjoyYourCoffee" and spaces = [5, 9]
• The character at index 5 is 'Y' and at index 9 is 'C'
• We insert spaces before these characters
• Output: "Enjoy Your Coffee"

The task is to return the modified string after all the spaces have been added at the specified positions.

Key points to understand:

• The indices in the spaces array refer to positions in the original string s
• Spaces are inserted before the character at each given index
• The spaces array is sorted in ascending order
• You need to build and return the new string with all spaces properly inserted

Intuition

When we need to insert spaces at specific positions in a string, we face a challenge: as we insert spaces, the indices of subsequent characters shift. For instance, if we insert a space at position 5, the character that was originally at position 9 would now be at position 10.

To avoid this index-shifting problem, we can build the result string from scratch rather than trying to insert spaces into the existing string. The key insight is to traverse the original string character by character while keeping track of where spaces need to be inserted.

Since the spaces array is sorted, we can use a pointer to track which space position we're currently looking for. As we iterate through each character in the original string:

• We check if the current index matches the next space position we need to handle
• If it matches, we add a space to our result before adding the current character
• We then move our space pointer forward to look for the next space position

This way, we only need to traverse the string once, checking at each position whether a space should be inserted. We're essentially merging two sequences: the characters from the original string and the spaces at their designated positions.

The beauty of this approach is that we don't need to worry about index adjustments or multiple string manipulations. We simply build the correct result in a single pass, making it both efficient and straightforward to implement.

Learn more about Two Pointers patterns.

Solution Approach

We implement a two-pointer approach to solve this problem efficiently in a single pass through the string.

Algorithm Steps:

1. Initialize data structures:

   • Create an empty list ans to build the result string character by character
   • Set pointer j = 0 to track our position in the spaces array

2. Iterate through the original string:

   • Use enumerate(s) to get both the index i and character c at each position
   • For each character position i:
     • Check if we need to insert a space: If j < len(spaces) (we haven't processed all spaces yet) AND i == spaces[j] (current position matches the next space position):
       • Append a space ' ' to ans
       • Increment j by 1 to move to the next space position
     • Add the current character: Append c to ans

3. Build and return the final string:

   • Use ''.join(ans) to convert the list of characters into the final string

Why this works:

• The pointer j ensures we process spaces in order since the spaces array is sorted
• By checking j < len(spaces) first, we avoid index out of bounds errors
• We only traverse the string once, achieving O(n) time complexity where n is the length of the string
• The space complexity is O(n) for storing the result

Example walkthrough with s = "EnjoyYourCoffee" and spaces = [5, 9]:

• At index 0-4: Add characters 'E', 'n', 'j', 'o', 'y' directly
• At index 5: i == spaces[0], so add space then 'Y', increment j to 1
• At index 6-8: Add 'o', 'u', 'r' directly
• At index 9: i == spaces[1], so add space then 'C', increment j to 2
• At index 10-14: Add remaining characters 'o', 'f', 'f', 'e', 'e'
• Result: "Enjoy Your Coffee"

Example Walkthrough

Let's walk through a small example: s = "HelloWorld" and spaces = [5]

Initial Setup:

• Original string: "HelloWorld" (length 10)
• Space should be inserted before index 5 (character 'W')
• Initialize: ans = [], j = 0

Step-by-step iteration:

Final Result: Join the list to get "Hello World"

The key insight: when we reach index 5, we first insert a space, then add 'W'. After processing this space position, we increment j so we won't check for spaces[0] again. Since j becomes 1 and len(spaces) = 1, the condition j < len(spaces) becomes false for all remaining iterations, so we simply add the rest of the characters without any more spaces.

Solution Implementation

Time and Space Complexity

The time complexity is O(n + m), where n is the length of the string s and m is the length of the array spaces. This is because:

• We iterate through each character in the string s exactly once, which takes O(n) time
• For each character, we check if the current index matches a value in spaces, and we traverse the spaces array at most once throughout the entire execution (using pointer j), which contributes O(m) time
• The total time is O(n) + O(m) = O(n + m)

The space complexity is O(n + m), where n is the length of the string s and m is the length of the array spaces. This is because:

• The ans list stores all characters from the original string (n characters) plus all the spaces we need to insert (m spaces in the worst case), resulting in O(n + m) space
• The final string created by ''.join(ans) also requires O(n + m) space
• Other variables like i, j, and c use constant space O(1)
• The total space complexity is O(n + m)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Managing Indices After Inserting Spaces

The Problem: A common mistake is trying to insert spaces directly into the string while iterating, which causes index shifting. For example:

# INCORRECT approach
def addSpaces(s, spaces):
    result = s
    for index in spaces:
        result = result[:index] + ' ' + result[index:]
    return result

This fails because after inserting the first space, all subsequent indices in the original spaces array become invalid. When you insert a space at position 5, the character that was at position 9 is now at position 10.

The Solution: Either adjust indices as you go (adding an offset for each inserted space) or use the two-pointer approach shown in the original solution that builds a new string from scratch.

Pitfall 2: String Concatenation Performance Issues

The Problem: Using string concatenation in a loop is inefficient in Python:

# INEFFICIENT approach
def addSpaces(s, spaces):
    result = ""
    space_index = 0
  
    for i, char in enumerate(s):
        if space_index < len(spaces) and i == spaces[space_index]:
            result += " "  # String concatenation
            space_index += 1
        result += char  # String concatenation
  
    return result

While this works correctly, string concatenation creates a new string object each time, leading to O(n²) time complexity for large strings.

The Solution: Use a list to collect characters and join them at the end, as shown in the original solution. This maintains O(n) time complexity since list append operations are O(1) amortized.

Pitfall 3: Forgetting Boundary Checks

The Problem: Accessing spaces[space_index] without checking if space_index < len(spaces) first:

# INCORRECT - can cause IndexError
for i, char in enumerate(s):
    if i == spaces[space_index]:  # Dangerous! No bounds check
        result.append(' ')
        space_index += 1
    result.append(char)

This throws an IndexError when space_index exceeds the length of the spaces array.

The Solution: Always check space_index < len(spaces) before accessing spaces[space_index]. The short-circuit evaluation of and ensures the second condition is only checked if the first is true.