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 stringafter the spaces have been added.

Examples

Example 1:

1
2
3
4
5

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 "LeetcodeH̲elpsM̲eL̲earn".
We then place spaces before those characters.

Example 2:

1
2
3
4
5

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 "ic̲odei̲np̲yt̲hon".
We then place spaces before those characters.

Example 3:

1
2
3
4

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

Method 1 - Using Two pointers with Stringbuilder

Here is the approach:

  1. Initial Setup: We first calculate the length of the resulting string after adding the spaces.
  2. Using Character Array: We’ll create a character array of the size of the resulting string and populate it with characters from s along with the spaces at the specified indices.
  3. Iteration: We iterate through the original string and the spaces array simultaneously to construct the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public String addSpaces(String s, int[] spaces) {
        StringBuilder ans = new StringBuilder();
        int n = s.length();
        int spaceIdx = 0;
        int m = spaces.length;
        
        for (int i = 0; i < n; i++) {
            // Check if the current index matches with any of the spaces array elements.
            if (spaceIdx < m && i == spaces[spaceIdx]) {
                ans.append(' ');
                spaceIdx++;
            }
            ans.append(s.charAt(i));
        }
        
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        ans: List[str] = []
        n: int = len(s)
        spaceIdx: int = 0
        m: int = len(spaces)
        
        for i in range(n):
            # Check if the current index matches with any of the spaces array elements.
            if spaceIdx < m and i == spaces[spaceIdx]:
                ans.append(" ")
                spaceIdx += 1
            ans.append(s[i])
        
        return "".join(ans)

Complexity

  • ⏰ Time complexity: O(n + m), where n is the length of the string and m is the length of the spaces array.
    • String Iteration: We iterate over each character of the string once.
    • Space Insertions: The number of space insertions is directly tied to the number of elements in the spaces array.
  • 🧺 Space complexity: O(n + m). Additional space proportional to the length of the string and the number of spaces.

Method 2 - Using Two Pointers with char array

Here is the approach:

  1. Initial Setup: We first calculate the length of the resulting string after adding the spaces.
  2. Using Character Array: We’ll create a character array of the size of the resulting string and populate it with characters from s along with the spaces at the specified indices.
  3. Iteration: We iterate through the original string and the spaces array simultaneously to construct the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public String addSpaces(String s, int[] spaces) {
        int n = s.length();
        int m = spaces.length;
        char[] ans = new char[n + m];
        int ansIdx = 0;
        int spaceIdx = 0;
        
        for (int i = 0; i < n; i++) {
            if (spaceIdx < m && i == spaces[spaceIdx]) {
                ans[ansIdx] = ' ';
                ansIdx++;
                spaceIdx++;
            }
            ans[ansIdx] = s.charAt(i);
            ansIdx++;
        }
        
        return new String(ans);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        n: int = len(s)
        m: int = len(spaces)
        ans: List[str] = [''] * (n + m)  # Create a list with the size of the resulting string
        ansIdx: int = 0
        spaceIdx: int = 0
        
        for i in range(n):
            if spaceIdx < m and i == spaces[spaceIdx]:
                ans[ansIdx] = ' '
                ansIdx += 1
                spaceIdx += 1
            ans[ansIdx] = s[i]
            ansIdx += 1
        
        return ''.join(ans)

Complexity

  • ⏰ Time complexity: O(n + m)
  • 🧺 Space complexity: O(n + m)