2109. Adding Spaces to a String - Detailed Explanation

Problem Statement

You are given a string s and an array of integers spaces. The array spaces contains indices (in strictly increasing order) where you need to insert a single space into s. In other words, for each index in spaces, you should insert a space character before the character at that index in the original string.

Return the modified string after all the spaces have been inserted.

Example 1

• Input:
  • s = "LeetcodeHelpsMeLearn"
  • spaces = [8, 13, 15]
• Explanation:
  • The characters at indices 8, 13, and 15 in the original string are where spaces must be inserted.
  • After inserting spaces:
    • Before index 8: "Leetcode" becomes "Leetcode "
    • Before index 13: "Helps" becomes "Helps "
    • Before index 15: "MeLearn" becomes "Me Learn"
  • The resulting string is: "Leetcode Helps Me Learn".
• Output: "Leetcode Helps Me Learn"

Example 2

• Input:
  • s = "spacing"
  • spaces = [1, 3, 5]
• Explanation:
  • Insert a space before the character at index 1, then at index 3, and then at index 5 of the original string.
  • The resulting string becomes: "s pa c ing" (visualized as characters with spaces inserted).
• Output: "s pa c ing"

Constraints

• 1 ≤ s.length ≤ 10⁵
• 1 ≤ spaces.length ≤ s.length
• 0 ≤ spaces[i] < s.length
• All values in spaces are unique and given in increasing order.

Hints

1. Two-Pointer Technique:

   • Use one pointer to iterate over the string s and another pointer to track the current index in the spaces array.
   • As you build the resulting string, whenever the current index in s matches the next index in spaces, insert a space and move to the next index in spaces.

2. String Building:

   • Since repeatedly concatenating strings is inefficient, consider building the result using a list (in Python) or a StringBuilder (in Java) and then converting it to a string.

3. Edge Cases:

   • Make sure to process the entire string even if you run out of indices in spaces.

Approach 1: Two-Pointer Iteration

Explanation

1. Initialization:

   • Create a pointer i for iterating over the string s.
   • Create a pointer j for the spaces array.
   • Use a list (or similar structure) to accumulate characters and spaces.

2. Iterate Over the String:

   • For each character at index i in s, check if i is equal to the current index in spaces (i.e. spaces[j]).
   • If it is, append a space to your result and move the spaces pointer (j++).
   • Append the current character to your result.
   • Continue this until you have processed all characters in s.

3. Finalize the Result:

   • Join the accumulated characters into the final string and return it.

This approach processes the string in a single pass, yielding a time complexity of O(n) where n is the length of the string.

Code Solutions

Python Code