2109. Adding Spaces to a String

MediumArrayStringSimulation
Leetcode Link

Problem Description

The problem presents us with a string s that is 0-indexed, which means the first character of the string is considered to be at position 0. We are also given an integer array spaces containing indices of the string s. We are tasked with modifying the string s by adding spaces at specific positions before each character indicated by the spaces array. The key here is to insert each space before the character at the given index. For instance, if s = "ExampleString" and spaces = [7], we should insert a space before the character at index 7 ('S'), resulting in "Example String".

To solve the problem, we have to iterate through the string, keep track of the indices where spaces need to be added, and make sure spaces are added before the characters at those indices.

Intuition

The intuition behind the solution is to create a new list to store the characters of the modified string including the spaces. We iterate through each character of the original string s, checking if the current index matches any element in the spaces array. If it does, we append a space to our answer list before appending the current character. The process is repeated for all characters in the original string. Since we're given that spaces is 0-indexed and every space is to be added before the character at the given index, we can iterate through s and spaces concurrently.

To implement this, we maintain two pointers:

  1. i to iterate through the string s.
  2. j to iterate through the spaces array.

As we go through the string with i, we compare i to the element at the current j index in spaces. If they match, it means we have to insert a space at the current position. We increment j to move to the next space index after a space is inserted, ensuring spaces are added in the proper sequence. Once a space is added or if no space is needed, we append the current character of s to the list. In the end, we convert the list to a string and return it as the final modified string with the added spaces.

Solution Approach

The solution approach involves iterating through the original string s while simultaneously keeping track of the space indices using the spaces array. The data structure used to store the result is a list, which is chosen due to its dynamic size and ease of insertion.

The algorithm follows these steps:

  1. Initialize an empty list called ans which will hold the characters of the new string with spaces.
  2. Use two pointers: i to go through each character in the string s, and j to access elements in the spaces array.
  3. Iterate over the string s with the help of the enumerate function which provides the index (i) and character (c) at each iteration.
  4. For each character iteration, check if the jth index of the spaces array is present (i.e., j < len(spaces)) and equals the current string index i.
  5. If the conditions are met, append a space (' ') to the ans list, indicating the point where a space needs to be added as per the spaces array.
  6. Increment the j pointer after adding a space to move to the next element of the spaces array.
  7. Append the current character c to the ans list.
  8. After the iteration is over, join all the characters in the ans list to form the modified string with spaces added at the specified indices.
  9. Return the joined string as the final result.

This approach ensures that each space is added in the right position before any corresponding character as specified by the indices in spaces. The use of a list for ans makes appending both spaces and characters straightforward as we iterate through the given string and indices.

The code associated with the approach is given in the reference solution:

1class Solution:
2    def addSpaces(self, s: str, spaces: List[int]) -> str:
3        ans = []
4        j = 0
5        for i, c in enumerate(s):
6            if j < len(spaces) and i == spaces[j]:
7                ans.append(' ')
8                j += 1
9            ans.append(c)
10        return ''.join(ans)

This approach is efficient due to the single pass over the string s and the direct mapping from the spaces array to the indices in the string.

Example Walkthrough

Let's go through an example to illustrate the solution approach. Consider the following input:

  • String s: "leetcode"
  • Spaces array spaces: [4, 7]

We want to modify the string by adding spaces at indices 4 and 7.

Here is a step-by-step walkthrough of the solution:

  1. Initialize an empty list named ans for building the result with spaces.

  2. Set two pointers, i at 0 to iterate through the string s, and j at 0 to iterate through the spaces array.

  3. Start iterating over each character of s. For this example, let's go through each iteration:

    • i = 0, c = 'l', j = 0 (Space not needed, ans becomes: ['l'])
    • i = 1, c = 'e', j = 0 (Space not needed, ans becomes: ['l', 'e'])
    • i = 2, c = 'e', j = 0 (Space not needed, ans becomes: ['l', 'e', 'e'])
    • i = 3, c = 't', j = 0 (Space not needed, ans becomes: ['l', 'e', 'e', 't'])
    • i = 4, c = 'c', j = 0 (Space needed, ans becomes: ['l', 'e', 'e', 't', ' '])
      • Increment j to 1 since we added a space.
    • i = 4, c = 'c', j = 1 (After space was added, ans becomes: ['l', 'e', 'e', 't', ' ', 'c'])
    • i = 5, c = 'o', j = 1 (Space not needed, ans becomes: ['l', 'e', 'e', 't', ' ', 'c', 'o'])
    • i = 6, c = 'd', j = 1 (Space not needed, ans becomes: ['l', 'e', 'e', 't', ' ', 'c', 'o', 'd'])
    • i = 7, c = 'e', j = 1 (Space needed, ans becomes: ['l', 'e', 'e', 't', ' ', 'c', 'o', 'd', ' '])
      • Increment j to 2 since we added a space.
    • i = 7, c = 'e', j = 2 (After space was added, ans becomes: ['l', 'e', 'e', 't', ' ', 'c', 'o', 'd', ' ', 'e'])
  4. After finishing the iteration, ans contains all the characters with spaces properly added: ['l', 'e', 'e', 't', ' ', 'c', 'o', 'd', ' ', 'e'].

  5. Convert the ans list into a string using ''.join(ans), which results in: "leet code ".

This is the final modified string, with spaces added at the right indices as per our spaces array. It accurately represents the original string with the required spaces inserted, demonstrating the effectiveness of the solution approach.

Python Solution

1class Solution:
2    def addSpaces(self, s: str, spaces: List[int]) -> str:
3        # Initialize an empty list to build the answer
4        answer = []
5        # Pointer to track the index within the 'spaces' list
6        space_index = 0
7      
8        # Iterate over the characters and indices of the input string 's'
9        for index, char in enumerate(s):
10            # Check if the current index matches the next space position
11            # and that we have not used all the provided spaces
12            if space_index < len(spaces) and index == spaces[space_index]:
13                # If so, append a space to the 'answer' list
14                answer.append(' ')
15                # Move the pointer to the next space position
16                space_index += 1
17            # Append the current character to the 'answer' list
18            answer.append(char)
19      
20        # Join all elements of 'answer' to get the final string with spaces
21        return ''.join(answer)
22

Java Solution

1class Solution {
2    // Method that adds spaces into a string at specified indices.
3    public String addSpaces(String s, int[] spaces) {
4        // StringBuilder is used for efficient string manipulation
5        StringBuilder result = new StringBuilder();
6      
7        // Use two pointers: 'i' for string 's', and 'j' for the spaces array
8        for (int i = 0, j = 0; i < s.length(); ++i) {
9            // Check if we have more spaces to add and if the current position matches the next space position
10            if (j < spaces.length && i == spaces[j]) {
11                // If so, append a space to the result
12                result.append(' ');
13                // Move to the next position in the spaces array
14                ++j;
15            }
16            // Append the current character from string 's'
17            result.append(s.charAt(i));
18        }
19      
20        // Return the modified string with spaces added
21        return result.toString();
22    }
23}
24

C++ Solution

1// The Solution class with a single method addSpaces to insert spaces into a string.
2class Solution {
3public:
4    // Given a string `inputString` and a vector `spacePositions` containing positions at which spaces are to be inserted,
5    // this function returns the string with spaces added at the specified positions.
6    string addSpaces(string inputString, vector<int>& spacePositions) {
7        // Initialize an empty string to store the result.
8        string result = "";
9
10        // iterate over each character in `inputString`.
11        // `charIndex` is the index of the current character, 
12        // `spaceIndex` is the index for iterating through `spacePositions`.
13        for (int charIndex = 0, spaceIndex = 0; charIndex < inputString.size(); ++charIndex) {
14            // If there are still positions left in `spacePositions` to process and
15            // the current character index matches the current space position,
16            // then add a space to 'result' and move to the next space position.
17            if (spaceIndex < spacePositions.size() && charIndex == spacePositions[spaceIndex]) {
18                result += ' ';
19                ++spaceIndex; // Move to the next position for a space.
20            }
21            // add the current character from `inputString` to `result`.
22            result += inputString[charIndex];
23        }
24      
25        // Return the resulting string with spaces inserted.
26        return result;
27    }
28};
29

Typescript Solution

1/**
2 * Inserts spaces into a string based on specified indices.
3 * 
4 * @param {string} str - The original string without spaces.
5 * @param {number[]} spaceIndices - An array of indices where spaces should be inserted.
6 * @returns {string} - The string with inserted spaces.
7 */
8function addSpaces(str: string, spaceIndices: number[]): string {
9    // Initialize an empty string to build the resulting string with spaces.
10    let resultStr = '';
11  
12    // Initialize variables to keep track of current indices in the string (strIndex) and
13    // space indices array (spaceIndex).
14    let strIndex = 0;
15    let spaceIndex = 0;
16  
17    // Iterate over each character in the original string.
18    while (strIndex < str.length) {
19        // If we have space indices left to process and the current string index matches
20        // the next space index, add a space to the result string.
21        if (spaceIndex < spaceIndices.length && strIndex === spaceIndices[spaceIndex]) {
22            resultStr += ' ';
23            // Move to the next space index after inserting a space.
24            spaceIndex++;
25        }
26        // Add the current character from the original string to the result string.
27        resultStr += str[strIndex];
28        // Move to the next character index.
29        strIndex++;
30    }
31  
32    // Return the result string with spaces added.
33    return resultStr;
34}
35

Time and Space Complexity

The given Python code snippet adds spaces in the specified indices of a string and is designed to have:

  • Time Complexity: The time complexity of the code is O(n), where n is the length of the string s. The enumerate function loops through the characters of the string s just once. For each character, the code checks if a space should be inserted before it, which is an O(1) operation since it just checks the current index against the current space index in spaces. The append operation for a list in Python has an average case time complexity of O(1), so appending either a character or a space doesn't significantly affect the time complexity. j increments at most len(spaces) times, which is independent of the length of s, so it does not change the overall time complexity dominated by the length of s.

  • Space Complexity: The space complexity is O(n), where n is the length of the string s. This is because a list ans is used to build the output string with spaces. In the worst case, the length of ans is equal to the length of s plus the number of spaces to insert. Since the number of spaces is at most n - 1 (a space after every character except the last one), the space complexity remains O(n) when considering both the input string and the additional spaces.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫