Adding Spaces to a String - Solution & Explanation
Problem Statement
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.
Approach Overview
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 1: Approach 1: Brute Force
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.
Complexity
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.
Approach 2: Approach 2: Optimized Solution Using Hash Map
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.
Complexity
Time Complexity: O(n) - linear time if hash lookups are constant time.
Space Complexity: O(n) - due to storage in the hash map.
Approach 3: Two Pointers
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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Adding Spaces to a String - Leetcode 2109 - Python • NeetCodeIO • 7,985 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Adding Spaces to a String easy or hard?
Adding Spaces to a String Python/Java solution
How to solve Adding Spaces to a String in O(n)?
What is the best approach for Adding Spaces to a String?
Is Adding Spaces to a String asked at Google/Amazon/Meta?
What data structure is used in Adding Spaces to a String?
What is the time complexity of Adding Spaces to a String?
Ready to solve this problem?
Practice Adding Spaces to a String with our built-in code editor and test cases.
Practice on FleetCode