Adding Spaces to a String solution and explanation
Google
9 more videos on this problem
Adding Spaces to a String - Leetcode 2109 - PythonNeetCodeIO · 7:46 · 7K views
Adding Spaces to a String | Straight Forward Easy | Leetcode 2109 | codestorywithMIKcodestorywithMIK · 7:07 · 5K views
Adding Spaces to a String | Leetcode 2109Techdose · 6:45 · 1K views
2109. Adding Spaces to a String | leetcode daily challenge | shashcode 3 | shashwatShashCode · 11:58 · 1K views
2109. Adding Spaces to a String (Leetcode Medium)Programming Live with Larry · 4:17 · 1K views
Adding Spaces to a String - LeetCode 2109 - Java Solutionalgobest - Computer Science · 3:21 · 1K views
Leetcode | 2109. Adding Spaces to a String | Medium | JavaDeveloper Docs · 4:35 · 282 views
LeetCode 2109 Adding Spaces to a String | String | Easy | Two Pointers | Amazon Interview QuestionCode Harmony · 8:18 · 235 views
Leetcode 2109 Adding Spaces to a StringMath Geeks · 2:03 · 191 views
2109. Adding Spaces to a String | Leetcode problem of the day | PythonThe CodeBreakz Show · 29:11 · 86 views
The problem
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.
def solve():
# Your brute-force logic here
print("Solution not implemented yet")
solve()public class Main {
public static void main(String[] args) {
solve();
}
static void solve() {
// Your brute-force logic here
System.out.println("Solution not implemented yet");
}
}#include <iostream>
void solve() {
// Your brute-force logic here
std::cout << "Solution not implemented yet" << std::endl;
}
int main() {
solve();
return 0;
}function solve() {
// Your brute-force logic here
console.log("Solution not implemented yet");
}
solve();#include <stdio.h>
void solve() {
// Your brute-force logic here
printf("Solution not implemented yet\n");
}
int main() {
solve();
return 0;
}using System;
class Program {
static void Main() {
solve();
}
static void solve() {
// Your brute-force logic here
Console.WriteLine("Solution not implemented yet");
}
}This Python script sets the stage for implementing a brute-force algorithm, which will be inefficient but straightforward.
Time Complexity: O(n^2) - represents a simple quadratic check.
Space Complexity: O(1) - no significant additional space is utilized.
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.
def solve():
# Implement optimized logic with hash map technique
print("Solution not implemented yet")
solve()import java.util.HashMap;
public class Main {
public static void main(String[] args) {
solve();
}
static void solve() {
// Implement optimized logic with hash map technique
System.out.println("Solution not implemented yet");
}
}#include <iostream>
#include <unordered_map>
void solve() {
// Implement optimized logic with hash map technique
std::cout << "Solution not implemented yet" << std::endl;
}
int main() {
solve();
return 0;
}function solve() {
// Implement optimized logic with hash map technique
console.log("Solution not implemented yet");
}
solve();#include <stdio.h>
#include <stdlib.h>
void solve() {
// Implement optimized logic with hash map technique
printf("Solution not implemented yet\n");
}
int main() {
solve();
return 0;
}using System;
using System.Collections.Generic;
class Program {
static void Main() {
solve();
}
static void solve() {
// Implement optimized logic with hash map technique
Console.WriteLine("Solution not implemented yet");
}
}This Python function aims to optimize the solution using dictionaries for fast data storage and retrieval.
Time Complexity: O(n) - hashmap allows constant time operations.
Space Complexity: O(n) - dictionary storage requirement.
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.
function addSpaces(s: string, spaces: number[]): string {
const ans: string[] = [];
for (let i = 0, j = 0; i < s.length; i++) {
if (i === spaces[j]) {
ans.push(' ');
j++;
}
ans.push(s[i]);
}
return ans.join('');
}func addSpaces(s string, spaces []int) string {
var ans []byte
for i, j := 0, 0; i < len(s); i++ {
if j < len(spaces) && i == spaces[j] {
ans = append(ans, ' ')
j++
}
ans = append(ans, s[i])
}
return string(ans)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force | Time Complexity: O(n^2) - represents a simple quadratic check. |
| Approach 2: Optimized Solution Using Hash Map | Time Complexity: O(n) - hashmap allows constant time operations. |
| Two Pointers | – |
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 |
Frequently asked questions
Is Adding Spaces to a String easy or hard?
Adding Spaces to a String is typically considered a medium-level problem. The core logic is straightforward string traversal, but recognizing the need for an O(n) construction approach instead of repeated insertions is the key optimization.
Adding Spaces to a String Python/Java solution
In Python, use a set for the indices and build the result with a list before joining it into a string. In Java, store indices in a HashSet and append characters to a StringBuilder while checking whether the current index requires a space.
How to solve Adding Spaces to a String in O(n)?
Store all indices from the spaces array in a hash set. Traverse the string once and build the result using a mutable buffer such as StringBuilder or a character list. When the current index exists in the set, append a space before adding the character, producing an O(n + k) linear-time solution.
What is the best approach for Adding Spaces to a String?
The best approach is a single-pass solution using a hash map or hash set containing the space indices. While iterating through the string, check whether the current index requires a space and append it before the character. This method runs in O(n + k) time and avoids expensive repeated string insertions.
Is Adding Spaces to a String asked at Google/Amazon/Meta?
String manipulation and simulation problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. While the exact problem may vary, the underlying pattern of scanning a string and inserting characters efficiently is common in coding interviews.
What data structure is used in Adding Spaces to a String?
The optimal approach uses a hash map or hash set to store indices where spaces should be inserted. This enables constant-time lookups during iteration. A dynamic string builder or character array is also used to efficiently construct the final result.
What is the time complexity of Adding Spaces to a String?
The optimal solution runs in O(n + k) time where n is the length of the string and k is the number of space positions. Each character is processed once and each lookup in the hash map is O(1). The brute force approach can degrade to O(n * k) due to repeated string reconstruction.