Adding Spaces to a String
MedPrompt
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 indices5and9respectively. 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 * 105sconsists only of lowercase and uppercase English letters.1 <= spaces.length <= 3 * 1050 <= spaces[i] <= s.length - 1- All the values of
spacesare strictly increasing.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Iterate through the
spacesarray from the last element to the first. This is crucial to avoid index shifting issues. - For each
indexinspaces:- Reconstruct the string
sby 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);
- Reconstruct the string
- After the loop completes, return the final modified string
s.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Create a
HashSet<Integer>and populate it with all values from thespacesarray. - Create an empty
StringBuilderto build the result. - Loop through the input string
sfrom indexi = 0tos.length() - 1. - Inside the loop, check if the current index
iis present in theHashSet. - If
set.contains(i), append a space" "to theStringBuilder. - Append the character
s.charAt(i)to theStringBuilder. - After the loop finishes, convert the
StringBuilderto a string and return it.
Walkthrough
The process is as follows:
- Transfer all indices from the
spacesarray into aHashSet. This takes O(m) time, wheremis the number of spaces, and allows for O(1) average time complexity for checking if an index needs a space. - Initialize a
StringBuilder, which is a mutable sequence of characters, making appends efficient. - Iterate through the original string
sfrom the beginning to the end. For each indexi, we first consult ourHashSet. Ifiis in the set, we append a space to ourStringBuilder. Then, we append the characters.charAt(i). - This single pass constructs the final string correctly and efficiently.
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(); }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize an empty
StringBuilder. - Initialize a pointer
spacePointer = 0for thespacesarray. - Loop through the input string
sfrom indexi = 0tos.length() - 1. - Inside the loop, check if
spacePointeris within the bounds ofspacesand ifspaces[spacePointer]is equal to the current string indexi. - If the condition is true, it means a space is needed before the current character. Append a space
" "to theStringBuilderand incrementspacePointerto look for the next space location. - Append the current character
s.charAt(i)to theStringBuilder. - After the loop, return the final string by calling
stringBuilder.toString().
Walkthrough
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.
// Main implementation using two pointersclass 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(); }}// Alternative implementation by appending substringsclass 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(); }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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(); }}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; }};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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.