Adding Spaces to a String

medium string two pointers

Problem

You are given a string s and a strictly increasing array spaces holding character positions. For every index in spaces, place a single space immediately before the character that currently sits at that index in the original string. Return the resulting string. Each value in spaces counts characters of the original s, so earlier insertions do not shift later targets.

Inputs = "ICodeInPython", spaces = [1, 5, 7]

Output"I Code In Python"

Spaces go before s[1]='C', s[5]='I', and s[7]='P', splitting the text into "I", "Code", "In", "Python".

spaces (comma-separated)

def add_spaces(s, spaces):
    out = []
    p = 0
    for i, ch in enumerate(s):
        if p < len(spaces) and spaces[p] == i:
            out.append(' ')
            p += 1
        out.append(ch)
    return ''.join(out)

function addSpaces(s, spaces) {
  const out = [];
  let p = 0;
  for (let i = 0; i < s.length; i++) {
    if (p < spaces.length && spaces[p] === i) {
      out.push(' ');
      p++;
    }
    out.push(s[i]);
  }
  return out.join('');
}

class Solution {
    public String addSpaces(String s, int[] spaces) {
        StringBuilder out = new StringBuilder();
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            if (p < spaces.length && spaces[p] == i) {
                out.append(' ');
                p++;
            }
            out.append(s.charAt(i));
        }
        return out.toString();
    }
}

string addSpaces(string s, vector<int>& spaces) {
    string out;
    int p = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (p < (int)spaces.size() && spaces[p] == i) {
            out.push_back(' ');
            p++;
        }
        out.push_back(s[i]);
    }
    return out;
}

Explanation

The naive approach would be to insert a space into the string at each target index. But inserting into the middle of a string shifts every later character, so the next target index would no longer point where we want — and each insertion can cost O(n), making the whole thing slow.

The clean fix is to never modify the original string. Instead we build the answer from scratch, copying characters one at a time, and drop in a space at exactly the right moments. Because spaces is already sorted, we only need a single pointer p into it.

We scan s with index i. Before appending the character at i, we check: does spaces[p] equal i? If yes, this character is the start of a new word, so we push a space first and advance p to the next target. Either way we then append the character itself. Since indices in spaces are measured against the original s and we never shift it, the matches line up perfectly.

Example: s = "ICodeInPython", spaces = [1, 5, 7]. At i = 0 we copy 'I'. At i = 1, spaces[0] == 1, so we add a space then 'C'. We keep copying until i = 5 where spaces[1] == 5, adding a space before 'I', and again at i = 7 before 'P'. The result is "I Code In Python".

Each character is touched once and each space is added once, so the build is linear in the size of the output.

Time: O(n + m) Space: O(n + m)