• Leetcode POTDs

Problem 2109 Adding Spaces to a String

Problem Statement

Link - Problem 2109

Question

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".

Return the 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.

Solution

class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        int total_size = s.size() + spaces.size();
        char result[total_size];
        int s_index = 0, spaces_index = 0, res_index = 0;

        while (s_index < s.size()) {
            if (spaces_index < spaces.size() && s_index == spaces[spaces_index]) {
                result[res_index++] = ' ';
                spaces_index++;
            }
            result[res_index++] = s[s_index++];
        }
        return string(result, total_size);
    }
};

Complexity Analysis

| Algorithm                                           | Time Complexity | Space Complexity |
| --------------------------------------------------- | --------------- | ---------------- |
| Modified two-pointer traversal for string insertion | O(n)            | O(n)             |

Explanation

Intial Thoughts

Think of the original string as a straight line without any spaces. The spaces array represents specific points where you want to introduce spaces. A natural approach could be to start from the beginning of the string and move through each character while also keeping track of the spaces we have to add. Another possible way could be to think of it as a sorting problem where you combine all the characters and spaces together in the correct order.

Intuitive Analysis

Intuitively, it feels like a two-pointer problem where you’re tracking both the current character in the string and the current space you need to add. The key insight is that you don’t actually need to physically separate these two lists – you can generate the resulting string on the fly by deciding whether to add a space or a character at each step. This results in a very efficient and clean solution without the need for explicit loops or extra memory allocations beyond what’s needed.

1. Intuition

• The problem requires adding spaces to a string at specific indices.
• We can solve this problem by iterating through the string and the indices simultaneously.
• We need to keep track of the current index in the string, the current index in the spaces array, and the current index in the result string.
• When the current index in the string matches the current index in the spaces array, we add a space to the result string.
• We can use a single loop to iterate through the string and the spaces array.
• This approach ensures that we add spaces at the correct indices in the string.
• This solution has a time complexity of O(n) and a space complexity of O(n).

2. Implementation

• We initialize the result string with a size equal to the sum of the string size and the spaces array size: int total_size = s.size() + spaces.size();
• We initialize three indices: s_index for the string, spaces_index for the spaces array, and res_index for the result string: int s_index = 0, spaces_index = 0, res_index = 0;
• We use a while loop to iterate through the string: while (s_index < s.size()) { ... }
• Inside the loop, we check if the current index in the string matches the current index in the spaces array: if (spaces_index < spaces.size() && s_index == spaces[spaces_index]) { ... }
• If it matches, we add a space to the result string and increment the spaces_index: result[res_index++] = ' '; spaces_index++;
• We then add the current character from the string to the result string and increment the s_index: result[res_index++] = s[s_index++];
• Finally, we return the result string: return string(result, total_size);

Complexity Analysis

Time Complexity:

• The time complexity is linear because we only iterate through the input string s once, using the while loop condition s_index < s.size(). This loop iterates s.size() times, and within each iteration, we perform constant-time operations.
• The dominant operations in the loop are result[res_index++] = ' '; and result[res_index++] = s[s_index++];, both of which take constant time. We perform a total of s.size() + spaces.size() assignments to result in the loop, plus some additional constant-time work to initialize the loop variables.
• Since the total number of iterations and constant-time operations within the loop grows linearly with the input size s.size(), we can express the time complexity as O(n + m), where n is the size of s and m is the size of spaces. Since Big O notation ignores lower-order terms, this simplifies to O(n + m), or simply O(n) when we consider the problem’s constraints, where m is the number of spaces and n is the size of the string, with m bounded by n.

Space Complexity:

• We use a character array result to store the final output, which requires O(n + m) space in the worst case, where n is the size of the string s and m is the size of spaces. However, since m is bounded by n, we can simplify this to O(n).
• The space required to store the loops’ indices s_index, spaces_index, and res_index does not grow with the input size and can be ignored when analyzing space complexity.
• No dynamic memory allocation is performed within the loop. The memory is allocated upfront for the result array, and then reused throughout the algorithm.

Footnote

This question is rated as Medium difficulty.

Hints

Create a new string, initially empty, as the modified string. Iterate through the original string and append each character of the original string to the new string. However, each time you reach a character that requires a space before it, append a space before appending the character.

Since the array of indices for the space locations is sorted, use a pointer to keep track of the next index to place a space. Only increment the pointer once a space has been appended.

Ensure that your append operation can be done in O(1).