2109. Adding Spaces To A String

Intuition

To solve this problem, we can process the input string and insert spaces at the specified indices efficiently

Approach: Two Pointers

Using two pointers, we can:

• Use one pointer to iterate over the input string s.
• Use another pointer to keep track of the current position in the spaces array.
• If the current character index matches the current space index from spaces, append a space to the result string and move the pointer in the spaces array. Otherwise, append the character to the result.
• Append the remaining characters in s after processing all indices in spaces.

Explanation:

1. Initialization:

2. Use ans to store the resulting string after inserting spaces.

3. Keep a pointer currSpace to track which space index to process next.

4. Iterate Through the String:

5. For each character in s, check if the current index matches the next space index in spaces.

6. If it does, append a space to ans and move the currSpace pointer.

7. Append the current character to ans.

8. Return result::

9. Convert the ans slice of bytes to a string and return it.

Complexity

• Time complexity: O(n + m) where:
• n is the length of the string s.
• m is the length of the spaces array.
• Space complexity: O(n + m) where n + m is the length of ans array.

Code

func addSpaces(s string, spaces []int) string {
    a := make([]uint8, 0, len(s) + len(spaces))
    for i, j := 0, 0; i < len(s); i++ {
        if j < len(spaces) && spaces[j] == i {
            a = append(a, ' ')
            j++
        }
        a = append(a, s[i])
    }
    return string(a)
}