Truncate Sentence

easy string scan

Problem

Given a sentence s and integer k, return the first k words of s, space-separated.

Inputs = "Hello how are you Contestant", k = 4

Output"Hello how are you"

Cut after the 4th word.

def truncate_sentence(s, k):
    out = []
    for c in s:
        if c == ' ':
            k -= 1
            if k == 0: break
        out.append(c)
    return ''.join(out)

function truncateSentence(s, k) {
  let out = '';
  for (const c of s) {
    if (c === ' ') {
      if (--k === 0) break;
    }
    out += c;
  }
  return out;
}

class Solution {
    public String truncateSentence(String s, int k) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == ' ' && --k == 0) break;
            sb.append(c);
        }
        return sb.toString();
    }
}

string truncateSentence(string s, int k) {
    string out;
    for (char c : s) {
        if (c == ' ' && --k == 0) break;
        out += c;
    }
    return out;
}

Explanation

We want the first k words of a sentence. Instead of splitting into a list of words and re-joining, we just copy characters one by one and count spaces to know where to stop.

Words are separated by single spaces, so the number of spaces tells us how many word boundaries we have crossed. Each time we hit a space we do k -= 1; when k reaches 0 it means we have just finished the kth word, so we break.

Notice the order: we decrement on the space and stop before adding that space to the output. Every non-space character (and any space that does not trigger the stop) is appended to out. At the end we join the collected characters into the answer.

This works because the kth word ends exactly at the space that drops k to zero, and we want everything up to but not including that space.

Example: "Hello how are you Contestant" with k = 4. The spaces after Hello, how, and are bring k down to 1, and the space after you makes k = 0, so we stop and return "Hello how are you".

Time: O(n) Space: O(n)