Problem Description

Given a string s and an integer array spaces, you need to insert a space before the character at each index specified in the spaces array. The spaces array is sorted in strictly increasing order, and all indices are valid (within the bounds of the string). Return the modified string after inserting the spaces.

Examples

Example 1:

Input: s = "LeetcodeHelpsMeLearn", spaces = [8,13,15]
Output: "Leetcode Helps Me Learn"

Example 2:

Input: s = "icodeinpython", spaces = [1,5,7,9]
Output: "i code in py thon"

Example 3:

Input: s = "spacing", spaces = [0,1,2,3,4,5,6]
Output: " s p a c i n g"

Solution Approach

The problem is straightforward to simulate. Since the spaces array is strictly increasing and all indices are valid, we can traverse the original string character by character. We maintain a pointer spacePtr to track the next index in the spaces array where a space should be inserted. For each character index i in the string, if i equals the current target index spaces[spacePtr], we append a space to the result before appending the current character, and then increment the pointer.

Algorithm

1. Initialize an empty StringBuilder for the result.
2. Initialize a pointer idx to 0 for traversing the spaces array.
3. Iterate over each character in the string by its index i:

• If idx is within the bounds of the spaces array and i == spaces[idx], append a space to the result and increment idx.
• Append the current character s.charAt(i) to the result.

15. Return the final string from the StringBuilder. Complexity Analysis

• Time Complexity: O(n), where n is the length of the string, as we traverse it once.
• Space Comlpexity: O(n) to the output string, assuming we cosnider the space required for the result. The auxiliary space used by the algorithm is O(1) excluding the output.

Code Implementation

public String insertSpaces(String s, int[] spaces) {
    StringBuilder result = new StringBuilder();
    int spaceIndex = 0;
    for (int i = 0; i < s.length(); i++) {
        if (spaceIndex < spaces.length && i == spaces[spaceIndex]) {
            result.append(' ');
            spaceIndex++;
        }
        result.append(s.charAt(i));
    }
    return result.toString();
}