Solution Explanation: Adding Spaces to a String

This problem involves inserting spaces into a string at specific indices provided in an integer array. The solution employs a two-pointer approach for efficient string manipulation.

Approach:

We use two pointers:

• i: Iterates through the input string s.
• j: Iterates through the spaces array, indicating where spaces should be added.

The algorithm proceeds as follows:

1. Initialization: Initialize an empty string or array ans to store the result. Set i and j to 0.

2. Iteration: Iterate through the input string s using pointer i.

3. Space Check: At each index i, check if it matches an index in the spaces array using pointer j. If i == spaces[j], it means a space should be added before the character at index i. Add a space to ans, and increment j to move to the next space index.

4. Character Append: Regardless of whether a space was added, append the character s[i] to ans. Increment i to move to the next character.

5. Termination: Continue this process until the entire string s has been processed (i reaches the end of s).

6. Return: Finally, convert ans (which might be an array of characters) into a string and return it.

Time Complexity Analysis:

The algorithm iterates through the string s once and the spaces array at most once. Therefore, the time complexity is O(m + n), where n is the length of the string s and m is the length of the spaces array. This is a linear time complexity.

Space Complexity Analysis:

The space complexity depends on the method used to build the resulting string. If we use an array to accumulate characters and then join them into a string, the space complexity becomes O(m + n) in the worst case (when all indices in spaces require spaces to be added). In-place modification isn't possible here because we're inserting new characters into the string, so extra space is required. If a string builder is used (as in Java's StringBuilder), the space complexity remains O(m + n) but might be slightly better in practice due to efficient memory management.

Code Examples (with slight variations based on language):

Python:

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        result = []
        space_index = 0
        for i, char in enumerate(s):
            if space_index < len(spaces) and i == spaces[space_index]:
                result.append(" ")
                space_index += 1
            result.append(char)
        return "".join(result)

Java:

class Solution {
    public String addSpaces(String s, int[] spaces) {
        StringBuilder sb = new StringBuilder();
        int spaceIndex = 0;
        for (int i = 0; i < s.length(); i++) {
            if (spaceIndex < spaces.length && i == spaces[spaceIndex]) {
                sb.append(" ");
                spaceIndex++;
            }
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

C++:

string addSpaces(string s, vector<int>& spaces) {
    string result = "";
    int spaceIndex = 0;
    for (int i = 0; i < s.length(); i++) {
        if (spaceIndex < spaces.size() && i == spaces[spaceIndex]) {
            result += " ";
            spaceIndex++;
        }
        result += s[i];
    }
    return result;
}
 

JavaScript:

const addSpaces = (s, spaces) => {
    let result = "";
    let spaceIndex = 0;
    for (let i = 0; i < s.length; i++) {
        if (spaceIndex < spaces.length && i === spaces[spaceIndex]) {
            result += " ";
            spaceIndex++;
        }
        result += s[i];
    }
    return result;
};

These examples all demonstrate the core two-pointer approach. The choice of using a list/array or a string builder is primarily a stylistic choice in most languages, though StringBuilder in Java and similar constructs in other languages offer better performance for large string manipulations.