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.

#2109

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

向字符串添加空格

给你一个下标从 0 开始的字符串 s ，以及一个下标从 0 开始的整数数组 spaces 。数组 spaces 描述原字符串中需要添加空格的下标。每个空格都应该插入到给定索引处的字符值之前。例如， s = "EnjoyYourCoffee" 且 spaces = [5, 9] ，那么我们需要…

数组双指针字符串模拟

题目描述

给你一个下标从 0 开始的字符串 s ，以及一个下标从 0 开始的整数数组 spaces 。

数组 spaces 描述原字符串中需要添加空格的下标。每个空格都应该插入到给定索引处的字符值之前。

例如，s = "EnjoyYourCoffee" 且 spaces = [5, 9] ，那么我们需要在 'Y' 和 'C' 之前添加空格，这两个字符分别位于下标 5 和下标 9 。因此，最终得到 "Enjoy Your Coffee" 。

请你添加空格，并返回修改后的字符串。

示例 1：

输入：s = "LeetcodeHelpsMeLearn", spaces = [8,13,15]
输出："Leetcode Helps Me Learn"
解释：
下标 8、13 和 15 对应 "LeetcodeHelpsMeLearn" 中加粗斜体字符。
接着在这些字符前添加空格。

示例 2：

输入：s = "icodeinpython", spaces = [1,5,7,9]
输出："i code in py thon"
解释：
下标 1、5、7 和 9 对应 "icodeinpython" 中加粗斜体字符。
接着在这些字符前添加空格。

示例 3：

输入：s = "spacing", spaces = [0,1,2,3,4,5,6]
输出：" s p a c i n g"
解释：
字符串的第一个字符前可以添加空格。

提示：

1 <= s.length <= 3 * 10⁵
s 仅由大小写英文字母组成
1 <= spaces.length <= 3 * 10⁵
0 <= spaces[i] <= s.length - 1
spaces 中的所有值 严格递增

lightbulb

解题思路

方法一：双指针

我们可以用双指针 $i$ 和 $j$ 分别指向字符串 $s$ 和数组 $\textit{spaces}$ 的头部，然后从头到尾遍历字符串 $s$ ，当 $i$ 等于 $\textit{spaces}[j]$ 时，我们往结果字符串中添加一个空格，然后 $j$ 自增 $1$ 。接下来，我们将 $s[i]$ 添加到结果字符串中，然后 $i$ 自增 $1$ 。继续这个过程，直到遍历完字符串 $s$ 。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n + m)$ 。其中 $n$ 和 $m$ 分别是字符串 $s$ 和数组 $spaces$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

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)

speed

复杂度分析

指标	值
时间	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.
空间	O(1)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2108 找出数组中的第一个回文字符串 #2105 给植物浇水 II #2149 按符号重排数组