Adding Spaces to a String

Problem Statement

In this programming problem, you are provided with a zero-indexed string named s and an array of integers referred to as spaces. This array contains indices that specify the exact positions in string s where spaces need to be added before the character present at each of the respective indices described in the spaces array. The primary task is to generate a new version of the string s where spaces are integrated at the designated indices dictated by the spaces array.

For instance, when given the string s = "EnjoyYourCoffee" and the array spaces = [5, 9], you are required to insert spaces immediately before the characters located at the 5th and 9th positions respectively. Thus transforming the original string to "Enjoy Your Coffee". The goal is to return this modified string after all specified spaces have been included.

Examples

Example 1

Input:

s = "LeetcodeHelpsMeLearn", spaces = [8,13,15]

Output:

"Leetcode Helps Me Learn"

Explanation:

The indices 8, 13, and 15 correspond to the underlined characters in "LeetcodeHelpsMeLearn". We then place spaces before those characters.

Example 2

Input:

s = "icodeinpython", spaces = [1,5,7,9]

Output:

"i code in py thon"

Explanation:

The indices 1, 5, 7, and 9 correspond to the underlined characters in "icodeinpython". We then place spaces before those characters.

Example 3

Input:

s = "spacing", spaces = [0,1,2,3,4,5,6]

Output:

" s p a c i n g"

Explanation:

We are also able to place spaces before the first character of the string.

Constraints

• 1 <= s.length <= 3 * 105
• s consists only of lowercase and uppercase English letters.
• 1 <= spaces.length <= 3 * 105
• 0 <= spaces[i] <= s.length - 1
• All the values of spaces are strictly increasing.

Approach and Intuition

This modification task requires careful handling of string manipulation and index management, especially as the insertion of spaces could potentially disrupt the indexing for subsequent insertions due to the expansion of the string length. Here’s a strategic approach:

1. Begin with reading the input string s and the spaces array.
2. Utilize a result container, such as a list, given that repeatedly appending to a string can be less efficient in many programming languages due to the immutability of string objects.
3. Traverse the string s using an index. For each index, determine if this index matches the current targeted index for space insertion from the spaces array.
4. If a match is found (i.e., the current index of the string matches the next index in the spaces list where a space should be inserted):
   • Append a space to the result container before appending the current character from the string s.
   • Move to the next index in the spaces array.
   • Otherwise, simply append the current character from s to the result container.
   • Continue this until the entire string has been processed.
5. After the loop, ensure any remaining characters in s are appended to the result container.
6. Convert the result container back to a string if necessary.
7. Return the newly formed string that includes the required spaces at specified positions.

Given this strategy, several noteworthy points come to the fore:

• Since each insertion point is unique and the array spaces is strictly increasing, there is no need to adjust future indices in the spaces array after an insertion. This simplifies the process and prevents potential errors linked with dynamic index adjustments.
• The utilization of a result container (like a list in Python) helps avoid performance hits that come with immutable string operations.
• The solution’s efficiency largely hinges on linearly moving through the string and the spaces array without unnecessary backtracking or redundant checks, making this approach optimal for large inputs as specified by the constraints.

Solutions

class Solution {
public:
    string insertSpaces(string str, vector<int>& indices) {
        string outputString;
        outputString.reserve(str.length() + indices.size());
    
        int idx = 0;
        for (int i = 0; i < str.length(); ++i) {
            if (idx < indices.size() && i == indices[idx]) {
                outputString += ' ';
                ++idx;
            }
            outputString += str[i];
        }
    
        return outputString;
    }
};