2109. Adding Spaces to a String

You are given a 0-indexed string s and a 0-indexed integer array spaces that describes the indices in the original string where spaces will be added. Each space should be inserted before the character at the given index.

• For example, given s = "EnjoyYourCoffee" and spaces = [5, 9], we place spaces before 'Y' and 'C', which are at indices 5 and 9 respectively. Thus, we obtain "Enjoy Your Coffee".

Returnthe modified string after the spaces have been added.

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 01:

#include <string>
#include <vector>
#include <unordered_map>

class Solution {
public:
    std::string addSpaces(const std::string &inputString, const std::vector<int> &spaces) {
        int charIndex = 0;
        std::string resultString;
        std::unordered_map<int, int> spaceMap;

        for (int spaceIndex : spaces) {
            spaceMap[spaceIndex]++;
        }

        for (char character : inputString) {
            if (spaceMap[charIndex] > 0) {
                resultString += ' ';
            }
            resultString += character;
            charIndex++;
        }

        return resultString;
    }
};

from collections import Counter
from typing import List

class Solution:
    def addSpaces(self, string: str, spaces: List[int]) -> str:
        charIndex = 0
        resultString = ''
        spaceMap = Counter(spaces)
        
        for character in string:
            if spaceMap[charIndex] > 0:
                resultString += ' '
            resultString += character
            charIndex += 1
        
        return resultString

Time Complexity

• Creating the space map:

  Iterating over the vector spaces to populate the unordered map takes \(O(S)\), where \(S\) is the size of the spaces vector.

• Processing the input string:

  The loop iterates over each character in inputString. Let the length of the input string be \(N\). For each character, the function checks the map and appends characters to the result string, which takes \(O(N)\).

• Overall Time Complexity:

  The overall time complexity is \(O(N + S)\), as the two operations are performed sequentially.

Space Complexity

• Space map:

  The unordered map spaceMap stores up to \(S\) keys, requiring \(O(S)\) space.

• Result string:

  The result string stores all characters from inputString and additional spaces. Its size is \(N + S\), requiring \(O(N + S)\) space.

• Overall Space Complexity:

  The overall space complexity is \(O(N + S)\), dominated by the result string and the space map.