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.
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 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 * 105s consists only of lowercase and uppercase English letters.1 <= spaces.length <= 3 * 1050 <= spaces[i] <= s.length - 1spaces are strictly increasing.Problem Overview: You are given a string s and an array spaces containing indices where spaces must be inserted. The task is to return a new string with spaces inserted before the characters at those positions while preserving the original order.
Approach 1: Brute Force Simulation (Time: O(n * k), Space: O(n + k))
The straightforward way is to simulate the insertion process. Iterate through the spaces array and insert a space at each specified index in the string. Because strings are immutable in many languages, each insertion typically creates a new string or shifts characters, making the operation expensive. If you repeatedly rebuild the string for every insertion, the cost accumulates to roughly O(n * k) where n is the string length and k is the number of spaces. This method works for small inputs and clearly demonstrates the problem mechanics, but it is inefficient for large strings.
Approach 2: Optimized Solution Using Hash Map (Time: O(n + k), Space: O(n + k))
A better strategy avoids repeated string modifications. Store all indices from spaces in a hash map (or hash set) for constant-time lookup. Then iterate through the string once while building the result using a dynamic buffer such as StringBuilder or a character list. At each index i, check if it exists in the map. If it does, append a space before adding s[i]. This transforms the problem into a single linear scan. Each character is processed once and each index lookup takes O(1), giving an overall complexity of O(n + k). This approach is essentially a clean simulation with constant‑time checks powered by a hash structure.
The iteration itself behaves like a lightweight two pointers pattern: one pointer walks through the string while another implicitly tracks the next space position. The solution also relies on efficient handling of string construction to avoid repeated reallocations.
Recommended for interviews: Interviewers expect the linear solution. Demonstrating the brute force approach first shows you understand the mechanics of inserting characters, but quickly moving to the hash lookup method proves you can optimize string processing problems. The optimal solution runs in O(n + k) time and scales well even when the string length approaches typical problem limits.
This approach involves checking all possible combinations or permutations to find the solution. Although it's straightforward and easy to implement, it may not be the most efficient way due to its high time complexity.
This C program sets up a framework for a brute-force solution. Currently, the logic is not implemented, but the structure is in place to solve the problem by iterating over possible solutions.
Time Complexity: O(n^2) - where n is the size of the input.
Space Complexity: O(1) - constant space usage as no additional data structures are used.
This approach uses a hash map to store intermediate results or counts, allowing for quicker lookup and more efficient processing, reducing the time complexity compared to the brute-force method.
This C program outlines the structure for utilizing a hash map approach to optimize solving the problem.
Time Complexity: O(n) - linear time if hash lookups are constant time.
Space Complexity: O(n) - due to storage in the hash map.
We can use two pointers i and j to point to the beginning of the string s and the array spaces, respectively. Then, we iterate through the string s from the beginning to the end. When i equals spaces[j], we add a space to the result string, and then increment j by 1. Next, we add s[i] to the result string, and then increment i by 1. We continue this process until we have iterated through the entire string s.
The time complexity is O(n + m), and the space complexity is O(n + m), where n and m are the lengths of the string s and the array spaces, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force | Time Complexity: O(n^2) - where n is the size of the input. |
| Approach 2: Optimized Solution Using Hash Map | Time Complexity: O(n) - linear time if hash lookups are constant time. |
| Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n * k) | O(n + k) | Useful for understanding the problem mechanics or when input sizes are very small |
| Hash Map / Set Lookup with Single Pass | O(n + k) | O(n + k) | Best general solution; efficient for large strings and commonly expected in interviews |
Adding Spaces to a String - Leetcode 2109 - Python • NeetCodeIO • 7,763 views views
Watch 9 more video solutions →Practice Adding Spaces to a String with our built-in code editor and test cases.
Practice on FleetCode