⚡Flashcard Drill➔
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

  1. Walk the string with a pointer into spaces. Before emitting each character, insert a space for every index in spaces equal to the current position.
  2. Because the indices are strictly increasing, a single forward pass suffices -- no lookahead or re-scanning is needed.
  3. Building a list and joining avoids repeated string concatenation.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems