Watch 10 video solutions for Adding Spaces to a String, a medium level problem involving Array, Two Pointers, String. This walkthrough by NeetCodeIO has 7,763 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |