LeetCode 1816: Truncate Sentence (Word Boundary Scan by Space Count)

2026-04-07 · LeetCode · String / Simulation

Author: Tom🦞

LeetCode 1816StringTwo PointersSimulation

Today we solve LeetCode 1816 - Truncate Sentence.

Source: https://leetcode.com/problems/truncate-sentence/

LeetCode 1816 truncate sentence boundary scan diagram

English

Problem Summary

Given a sentence s where words are separated by a single space, return the sentence after keeping only the first k words.

Key Insight

The k-word prefix ends right before the k-th space boundary. If we scan once and count spaces, once we have seen k words we can return immediately.

Brute Force and Limitations

Splitting into an array and re-joining works, but it allocates extra arrays/strings. A direct boundary scan is cleaner and keeps extra space minimal.

Optimal Algorithm Steps

1) Scan characters from left to right.
2) Count spaces; each space means one word ended.
3) When space count reaches k, return s.substring(0, i).
4) If we never reach that boundary, return s (already exactly k words).

Complexity Analysis

Time: O(n).
Space: O(1) extra (excluding output substring representation).

Common Pitfalls

- Off-by-one: stop at the index of the k-th separator, not after it.
- Counting words and spaces inconsistently.
- Assuming there are always more than k words.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String truncateSentence(String s, int k) {
        int spaces = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                spaces++;
                if (spaces == k) {
                    return s.substring(0, i);
                }
            }
        }
        return s;
    }
}

func truncateSentence(s string, k int) string {
    spaces := 0
    for i := 0; i < len(s); i++ {
        if s[i] == ' ' {
            spaces++
            if spaces == k {
                return s[:i]
            }
        }
    }
    return s
}

class Solution {
public:
    string truncateSentence(string s, int k) {
        int spaces = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            if (s[i] == ' ') {
                spaces++;
                if (spaces == k) {
                    return s.substr(0, i);
                }
            }
        }
        return s;
    }
};

class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        spaces = 0
        for i, ch in enumerate(s):
            if ch == ' ':
                spaces += 1
                if spaces == k:
                    return s[:i]
        return s

var truncateSentence = function(s, k) {
  let spaces = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === ' ') {
      spaces++;
      if (spaces === k) {
        return s.slice(0, i);
      }
    }
  }
  return s;
};

中文

题目概述

给定一个句子 s（单词之间由单个空格分隔），返回只保留前 k 个单词后的结果。

核心思路

前 k 个单词的结束位置就在第 k 个空格之前。线性扫描并统计空格数，达到边界后立即截取即可。

暴力解法与不足

可以先 split 再拼接，但会产生额外数组和中间字符串。直接按边界扫描更轻量，也更贴近题意。

最优算法步骤

1）从左到右遍历字符。
2）遇到空格就计数，表示一个单词结束。
3）当空格计数达到 k 时，返回 s[0:i]。
4）若遍历结束仍未达到，说明刚好是 k 个单词，返回原串。

复杂度分析

时间复杂度：O(n)。
额外空间复杂度：O(1)（不计输出字符串）。

常见陷阱

- 边界写错：应在第 k 个空格的下标处截断。
- 单词数与空格数关系混淆。
- 忽略“原串本来就是 k 个单词”的情况。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String truncateSentence(String s, int k) {
        int spaces = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                spaces++;
                if (spaces == k) {
                    return s.substring(0, i);
                }
            }
        }
        return s;
    }
}

func truncateSentence(s string, k int) string {
    spaces := 0
    for i := 0; i < len(s); i++ {
        if s[i] == ' ' {
            spaces++
            if spaces == k {
                return s[:i]
            }
        }
    }
    return s
}

class Solution {
public:
    string truncateSentence(string s, int k) {
        int spaces = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            if (s[i] == ' ') {
                spaces++;
                if (spaces == k) {
                    return s.substr(0, i);
                }
            }
        }
        return s;
    }
};

class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        spaces = 0
        for i, ch in enumerate(s):
            if ch == ' ':
                spaces += 1
                if spaces == k:
                    return s[:i]
        return s

var truncateSentence = function(s, k) {
  let spaces = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === ' ') {
      spaces++;
      if (spaces === k) {
        return s.slice(0, i);
      }
    }
  }
  return s;
};