LeetCode 2109 - Adding Spaces to a String

The problem requires us to insert spaces into a given string s at specific positions described by the array spaces. Each element in spaces represents an index in the string before which a space should be inserted.

leetcodemediumarraytwo-pointersstringsimulation

LeetCode Problem 2109

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, String, Simulation

Solution

Problem Understanding

The problem requires us to insert spaces into a given string s at specific positions described by the array spaces. Each element in spaces represents an index in the string before which a space should be inserted. For example, if spaces = [2] and s = "hello", the output would be "he llo".

The input string s can be up to 300,000 characters long, and the spaces array can also contain up to 300,000 indices. All indices in spaces are strictly increasing, which means we will never have duplicate positions and we can traverse spaces in a single pass while iterating through the string.

Important edge cases include inserting a space before the very first character, inserting spaces consecutively, and having spaces cover all characters of the string. The problem guarantees strictly increasing indices, so we do not need to handle duplicates or unordered indices.

The expected output is a string where the spaces have been inserted exactly at the positions indicated by the spaces array.

Approaches

The brute-force approach is to iterate through the spaces array and repeatedly insert spaces into the string using slicing operations. Each insertion creates a new string because strings are immutable. While this is correct, it is inefficient because inserting into a string repeatedly has O(n) cost per insertion. With m spaces and a string of length n, the total time complexity can reach O(n * m), which is far too slow for the constraints (up to 300,000 characters and indices).

The optimal approach leverages the fact that strings are immutable but lists are not. We can iterate through the string once, appending each character to a list. Using a pointer on the spaces array, we insert a space whenever the current index matches the next element in spaces. This ensures O(n + m) time complexity with O(n + m) additional space to construct the final string. This approach uses a single pass and avoids repeated string concatenation.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(n) Insert spaces one by one using string slicing; inefficient for large input
Optimal O(n + m) O(n + m) Iterate once through string with a pointer on spaces to insert spaces efficiently

Algorithm Walkthrough

  1. Initialize a list result to hold the characters and spaces of the final string. Lists are used because appending to a list is O(1) on average, unlike string concatenation.
  2. Initialize a pointer space_index at 0 to track our current position in the spaces array.
  3. Iterate through the string s using an index i.
  4. At each index i, check if space_index is within bounds and if spaces[space_index] == i. If so, append a space to result and increment space_index.
  5. Append the character s[i] to result.
  6. Continue until all characters have been processed.
  7. Join the list result into a single string and return it.

Why it works: The pointer through spaces ensures we only add spaces exactly at the specified indices. Because spaces is strictly increasing, we never insert a space twice at the same position. The invariant is that result always contains the correctly spaced characters for all indices up to i.

Python Solution

from typing import List

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        result = []
        space_index = 0
        for i, char in enumerate(s):
            if space_index < len(spaces) and spaces[space_index] == i:
                result.append(' ')
                space_index += 1
            result.append(char)
        return ''.join(result)

The code creates a list result to efficiently build the final string. The pointer space_index ensures that we only check the next relevant space. Each character is processed once, and a space is added only when required, producing an O(n + m) solution.

Go Solution

func addSpaces(s string, spaces []int) string {
    result := make([]byte, 0, len(s)+len(spaces))
    spaceIndex := 0
    for i := 0; i < len(s); i++ {
        if spaceIndex < len(spaces) && spaces[spaceIndex] == i {
            result = append(result, ' ')
            spaceIndex++
        }
        result = append(result, s[i])
    }
    return string(result)
}

The Go version mirrors the Python solution. We preallocate the slice capacity to avoid multiple resizes. The iteration logic is the same: use a pointer to track the next space, append characters to the slice, and convert to string at the end.

Worked Examples

Example 1:

Input: s = "LeetcodeHelpsMeLearn", spaces = [8,13,15]

i char space_index result
0 L 0 L
1 e 0 Le
... ... ... ...
8 H 0 Leetcode H
13 M 1 Leetcode Helps M
15 L 2 Leetcode Helps Me L

Output: "Leetcode Helps Me Learn"

Example 2:

Input: s = "icodeinpython", spaces = [1,5,7,9]

Following the same process produces: "i code in py thon"

Example 3:

Input: s = "spacing", spaces = [0,1,2,3,4,5,6]

Each character gets a preceding space, output: " s p a c i n g"

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Iterate through string (n) and spaces (m) once with a pointer
Space O(n + m) Store the resulting string in a list/slice with spaces

The time complexity is linear with respect to the size of the string and the number of spaces because we traverse each exactly once. Space complexity includes the original string length plus the number of spaces added.

Test Cases

# Provided examples
assert Solution().addSpaces("LeetcodeHelpsMeLearn", [8,13,15]) == "Leetcode Helps Me Learn"
assert Solution().addSpaces("icodeinpython", [1,5,7,9]) == "i code in py thon"
assert Solution().addSpaces("spacing", [0,1,2,3,4,5,6]) == " s p a c i n g"

# Edge cases
assert Solution().addSpaces("a", [0]) == " a"  # single character, space before it
assert Solution().addSpaces("ab", [0,1]) == " a b"  # consecutive spaces
assert Solution().addSpaces("hello", []) == "hello"  # no spaces
assert Solution().addSpaces("world", [4]) == "worl d"  # space at last character
Test Why
"LeetcodeHelpsMeLearn", [8,13,15] Normal multiple spaces in the middle
"icodeinpython", [1,5,7,9] Normal spaced insertion
"spacing", [0,1,2,3,4,5,6] Spaces before all characters
"a", [0] Single character, space before first
"ab", [0,1] Consecutive spaces
"hello", [] No spaces, identity case
"world", [4] Space at last character

Edge Cases

One important edge case is inserting a space before the first character of the string. A naive solution might assume the first character should never be preceded by a space. The algorithm handles this correctly by checking the current index against spaces.

Another edge case is when spaces contains consecutive indices. For example, spaces = [0,1,2] with s = "abc" should output " a b c". Using a single pointer ensures each space is inserted precisely once at the correct position.

The third edge case is when the last character is preceded by a space. For example, spaces = [n-1]. The solution correctly appends a space when the index equals the last element of spaces, ensuring the space is added at the very end before the last character.

This approach covers all edge cases guaranteed by the problem constraints, including strictly increasing space indices and the maximum input size.