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.
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(); }}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.