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"
andspaces = [5, 9]
, we place spaces before'Y'
and'C'
, which are at indices5
and9
respectively. Thus, we obtain"Enjoy **_Y_** our _**C**_ offee"
.
Return****the modified stringafter the spaces have been added.
Examples
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 "LeetcodeH̲elpsM̲eL̲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 "ic̲odei̲np̲yt̲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.
Solution
Method 1 - Using Two pointers with Stringbuilder
Here is the approach:
- Initial Setup: We first calculate the length of the resulting string after adding the spaces.
- 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. - Iteration: We iterate through the original string and the
spaces
array simultaneously to construct the result.
Code
Java
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();
}
}
Python
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)
, wheren
is the length of the string andm
is the length of thespaces
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:
- Initial Setup: We first calculate the length of the resulting string after adding the spaces.
- 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. - Iteration: We iterate through the original string and the
spaces
array simultaneously to construct the result.
Code
Java
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);
}
}
Python
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)