# Adding Spaces to a String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/adding-spaces-to-a-string)
Canonical: https://scaleengineer.com/dsa/problems/adding-spaces-to-a-string
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array, String
---
## Problem
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 **Y**our **C**offee"`.

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 "Leetcode**H**elps**M**e**L**earn".
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 "i**c**ode**i**n**p**y**t**hon".
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**.

# Approaches
## Brute Force with String Concatenation
This naive approach involves directly manipulating the string for each space that needs to be added. We iterate through the given `spaces` indices and, for each index, insert a space into the string. Since strings in many languages (like Java) are immutable, each insertion operation requires creating a new string. This leads to very poor performance, especially for large strings.
**Time:** O(m * n), where `n` is the length of the string and `m` is the number of spaces. Each string concatenation and substring operation can take up to O(n + k) time, where `k` is the number of spaces already added. This results in a time complexity that is roughly quadratic. · **Space:** O(m * n) in the worst case. Each modification creates a new string, and the string length grows. The intermediate strings can consume a large amount of memory.
**Pros:** Conceptually simple and easy to understand.
**Cons:** Extremely inefficient due to repeated creation of new string objects.; The time complexity is quadratic, which will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
To correctly implement this, we must process the space indices in reverse order. If we were to process them in ascending order, inserting a space at an early index (e.g., index 5) would shift all subsequent characters, making the later indices in the `spaces` array invalid for the modified string. By iterating from the largest index to the smallest, we ensure that each insertion does not affect the positions of the characters for the remaining insertions.

For each `space_index` in the reversed `spaces` array, we create a new string by concatenating the part of the string before `space_index`, a space character, and the part of the string from `space_index` to the end. This process is repeated for all space indices.

```java
class Solution {
    public String addSpaces(String s, int[] spaces) {
        // This approach is very slow and will cause Time Limit Exceeded.
        // It's for demonstration of a naive solution.
        for (int i = spaces.length - 1; i >= 0; i--) {
            int index = spaces[i];
            s = s.substring(0, index) + " " + s.substring(index);
        }
        return s;
    }
}
```
### Algorithm
- Iterate through the `spaces` array from the last element to the first. This is crucial to avoid index shifting issues.
- For each `index` in `spaces`:
    - Reconstruct the string `s` by taking the substring before the index, adding a space, and then appending the substring from the index onwards.
    - In Java, this would look like: `s = s.substring(0, index) + " " + s.substring(index);`
- After the loop completes, return the final modified string `s`.

## Using a HashSet and StringBuilder
A much better approach is to avoid repeated string modifications. We can first store all the space indices in a data structure that allows for fast lookups, such as a `HashSet`. Then, we can iterate through the original string just once, building a new string with a `StringBuilder`. For each character, we check if its index is one where a space should be inserted.
**Time:** O(n + m), where `n` is the length of `s` and `m` is the length of `spaces`. It takes O(m) to build the set and O(n) to iterate through the string, with each check and append taking constant time on average. · **Space:** O(n + m). We need O(m) space for the `HashSet` and O(n + m) space for the `StringBuilder` that holds the final result.
**Pros:** Efficient with a linear time complexity of O(n + m).; Significantly outperforms the brute-force approach.
**Cons:** Uses extra space for the `HashSet`, which is O(m). While efficient, a more space-optimized solution exists.
### Explanation
The process is as follows:
1.  Transfer all indices from the `spaces` array into a `HashSet`. This takes O(m) time, where `m` is the number of spaces, and allows for O(1) average time complexity for checking if an index needs a space.
2.  Initialize a `StringBuilder`, which is a mutable sequence of characters, making appends efficient.
3.  Iterate through the original string `s` from the beginning to the end. For each index `i`, we first consult our `HashSet`. If `i` is in the set, we append a space to our `StringBuilder`. Then, we append the character `s.charAt(i)`.
4.  This single pass constructs the final string correctly and efficiently.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public String addSpaces(String s, int[] spaces) {
        Set<Integer> spaceIndices = new HashSet<>();
        for (int space : spaces) {
            spaceIndices.add(space);
        }
        
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (spaceIndices.contains(i)) {
                result.append(" ");
            }
            result.append(s.charAt(i));
        }
        
        return result.toString();
    }
}
```
### Algorithm
- Create a `HashSet<Integer>` and populate it with all values from the `spaces` array.
- Create an empty `StringBuilder` to build the result.
- Loop through the input string `s` from index `i = 0` to `s.length() - 1`.
- Inside the loop, check if the current index `i` is present in the `HashSet`.
- If `set.contains(i)`, append a space `" "` to the `StringBuilder`.
- Append the character `s.charAt(i)` to the `StringBuilder`.
- After the loop finishes, convert the `StringBuilder` to a string and return it.

## Single Pass with StringBuilder (Optimal)
The most optimal approach takes advantage of the fact that the `spaces` array is already sorted. This allows us to build the final string in a single pass without any extra data structures for lookups. We can use a two-pointer technique: one pointer for the current position in the string `s`, and another for the current position in the `spaces` array.
**Time:** O(n + m). We iterate through the string of length `n` once, and the pointer for the `spaces` array of length `m` also traverses its array once. The total work is proportional to the sum of the lengths. · **Space:** O(n + m). The space is dominated by the `StringBuilder` used to construct the result string, which will have a final length of `n + m`. This is optimal as the output itself requires this much space.
**Pros:** Most efficient in both time and space.; Avoids the overhead of creating and populating a `HashSet`.; Builds the result string in a single, linear pass.
**Cons:** None. This is the optimal solution for the problem.
### Explanation
We iterate through the string `s` with a pointer `i` and maintain a second pointer `j` for the `spaces` array. As we build the result in a `StringBuilder`, we compare `i` with `spaces[j]`. If they are equal, it's time to insert a space. We append the space and advance `j` to the next index in the `spaces` array. Then, we append the character `s.charAt(i)`. This ensures that spaces are inserted at the correct positions in one go.

An alternative but equally optimal implementation involves iterating through the `spaces` array and appending substrings of `s` to the `StringBuilder`. Both methods are highly efficient.

```java
// Main implementation using two pointers
class Solution {
    public String addSpaces(String s, int[] spaces) {
        StringBuilder result = new StringBuilder();
        int spacePointer = 0;
        for (int i = 0; i < s.length(); i++) {
            if (spacePointer < spaces.length && spaces[spacePointer] == i) {
                result.append(" ");
                spacePointer++;
            }
            result.append(s.charAt(i));
        }
        return result.toString();
    }
}
```

```java
// Alternative implementation by appending substrings
class Solution {
    public String addSpaces(String s, int[] spaces) {
        StringBuilder result = new StringBuilder();
        int prevIndex = 0;
        for (int spaceIndex : spaces) {
            result.append(s.substring(prevIndex, spaceIndex));
            result.append(" ");
            prevIndex = spaceIndex;
        }
        result.append(s.substring(prevIndex));
        return result.toString();
    }
}
```
### Algorithm
- Initialize an empty `StringBuilder`.
- Initialize a pointer `spacePointer = 0` for the `spaces` array.
- Loop through the input string `s` from index `i = 0` to `s.length() - 1`.
- Inside the loop, check if `spacePointer` is within the bounds of `spaces` and if `spaces[spacePointer]` is equal to the current string index `i`.
- If the condition is true, it means a space is needed before the current character. Append a space `" "` to the `StringBuilder` and increment `spacePointer` to look for the next space location.
- Append the current character `s.charAt(i)` to the `StringBuilder`.
- After the loop, return the final string by calling `stringBuilder.toString()`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  string addSpaces(string s, vector<int> &spaces) {
    string ans = "";
    for (int i = 0, j = 0; i < s.size(); ++i) {
      if (j < spaces.size() && i == spaces[j]) {
        ans += ' ';
        ++j;
      }
      ans += s[i];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str: ans = [] j = 0 for i, c in enumerate(s): if j < len(spaces) and i == spaces[j]: ans . append(' ') j += 1 ans . append(c) return '' . join(ans)

```