NeetCode #195LC-2109MediumTwo Pointers
← Back to All Problems#195 · #2109 · Adding Spaces to a String(向字符串添加空格)
📌 Problem Statement & Constraints
You are given a 0-indexed string
s and a 0-indexed integer array spaces listing the indices at which spaces should be inserted. Return the resulting string. The indices are strictly increasing. Constraints: 1 <= s.length <= 3 * 10^5, 0 <= spaces[i] < s.length.💡 Core Algorithmic Approaches
- Walk the string with a pointer into
spaces. Before emitting each character, insert a space for every index inspacesequal to the current position. - Because the indices are strictly increasing, a single forward pass suffices -- no lookahead or re-scanning is needed.
- Building a list and joining avoids repeated string concatenation.
- Inserting spaces by rebuilding the string with slices would be O(n * k) because of repeated copies.
💻 Benchmark Python3 Implementation
class Solution:
def addSpaces(self, s: str, spaces: List[int]) -> str:
res = []
sp = 0
for i, ch in enumerate(s):
while sp < len(spaces) and spaces[sp] == i:
res.append(" ") # insert before position i
sp += 1
res.append(ch)
return "".join(res)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + k): each character and each space is emitted once.
💾 Space Complexity
O(n + k) for the result.
⚠️ Interview Pitfalls & Follow-ups
- Rebuilding with
s[:i] + " " + s[i:]in a loop: each rebuild is O(n), giving O(n * k). - Not exploiting the strictly increasing order of
spaces: a pointer is all that is needed; sorting or searching is wasted work. - Inserting spaces after the character: the insertion index refers to the position before the character at that index.
- Using
spaces[sp] <= i: with strictly increasing indices and a single pass, equality is the correct test, and using<=would be harmless but misleading.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.