#2109

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Adding Spaces to a String

Learn to efficiently insert spaces in a string using two-pointer scanning with invariant tracking in linear time.

Problem Statement

Given a 0-indexed string s and a 0-indexed integer array spaces, insert a space before each index listed in spaces. The spaces array is strictly increasing, and each value indicates the position in the original string where a new space should appear.

Return the resulting string after all spaces have been inserted. For example, with s = "LeetcodeHelpsMeLearn" and spaces = [8,13,15], the output should be "Leetcode Helps Me Learn". The goal is to perform this efficiently using a two-pointer scanning strategy.

Examples

Example 1

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

Output: "Leetcode Helps Me Learn"

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"

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"

We are also able to place spaces before the first character of the string.

Constraints

1 <= s.length <= 3 * 105
s consists only of lowercase and uppercase English letters.
1 <= spaces.length <= 3 * 105
0 <= spaces[i] <= s.length - 1
All the values of spaces are strictly increasing.

Solution Approach

Two-pointer linear scan

Use one pointer for the original string and one for the spaces array. Iterate through s, appending each character to a result string. Whenever the string pointer matches the current space index, append a space first, then continue scanning.

Maintain invariant

Always ensure the space pointer only moves forward and tracks the next space to insert. This invariant prevents missing any spaces and guarantees correctness without revisiting characters.

Single-pass construction

Construct the final string in one pass, appending characters and spaces as needed. This avoids extra memory allocations or repeated string concatenation, maintaining O(n + m) time complexity.

Complexity Analysis

Metric	Value
Time	O(n + m)
Space	O(1)

Time complexity is O(n + m) where n is the length of the string and m is the number of spaces, because each character and space index is processed once. Space complexity is O(1) extra if using a string builder approach, aside from the output string.

What Interviewers Usually Probe

Are you handling the strictly increasing order of spaces correctly?
Can you maintain a pointer invariant to insert spaces efficiently?
Will your solution scale to maximum string length without extra passes?

Common Pitfalls or Variants

Common pitfalls

Forgetting to append a space before the first character when the first space index is 0.
Incorrectly moving the space pointer, causing missing or extra spaces.
Building the output string inefficiently with repeated concatenation leading to higher time complexity.

Follow-up variants

Insert a different character or delimiter instead of a space at specified indices.
Spaces array could contain duplicates, requiring merging consecutive inserts.
Given a stream of characters, insert spaces dynamically while reading the stream.

FAQ

What is the best approach for Adding Spaces to a String?

Using two-pointer scanning with invariant tracking allows a single-pass construction of the string while inserting spaces correctly.

Can this method handle spaces at the beginning of the string?

Yes, the algorithm inserts a space whenever the pointer matches the space index, including index 0, without extra handling.

What is the time complexity of the two-pointer method?

The time complexity is O(n + m), where n is the string length and m is the number of spaces, since each element is processed once.

Do I need extra memory for this approach?

Aside from the resulting string, extra memory is minimal if using a string builder or similar structure, achieving O(1) additional space.

Why is invariant tracking important in Adding Spaces to a String?

Maintaining an invariant for the next space index ensures no space is skipped or duplicated, preserving correctness for strictly increasing indices.

terminal

Solution

Solution 1: Two Pointers

We can use two pointers $i$ and $j$ to point to the beginning of the string $s$ and the array $\textit{spaces}$, respectively. Then, we iterate through the string $s$ from the beginning to the end. When $i$ equals $\textit{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$.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#2108 find first palindromic string in the array #2105 watering plants ii #2149 rearrange array elements by sign