LeetCode 1816 - Truncate Sentence

Difficulty: 🟢 Easy
Topics: Array, String

Solution

Problem Understanding

The problem gives us a sentence s and an integer k. A sentence is guaranteed to contain words separated by exactly one space, with no extra spaces at the beginning or end. Our task is to return a new sentence that contains only the first k words from the original sentence.

In other words, we need to cut the sentence off after the kth word and ignore everything that comes after it.

For example, if the input sentence is:

"Hello how are you Contestant"

and k = 4, then the first four words are:

"Hello", "how", "are", "you"

So the correct output becomes:

"Hello how are you"

The input size is very small. The maximum length of the string is only 500 characters, which means almost any straightforward string-processing solution will be fast enough. Because of this, the focus of the problem is correctness and clean implementation rather than advanced optimization.

The constraints also guarantee several important properties:

Words are separated by exactly one space.
There are no leading or trailing spaces.
k is always valid, meaning there are at least k words in the sentence.
Words contain only English letters.

These guarantees simplify the implementation significantly because we do not need to handle malformed input, multiple consecutive spaces, or missing words.

There are still a few edge cases worth thinking about:

When k equals the total number of words, the answer should be the original sentence unchanged.
When k = 1, the result should contain only the first word.
Very short sentences should still work correctly.
A naive implementation could accidentally leave trailing spaces if it manually builds the result string incorrectly.

Approaches

Brute Force Approach

A straightforward solution is to split the sentence into an array of words using spaces as delimiters. Once we have the list of words, we take the first k words and join them back together with spaces.

This approach is easy to understand because it directly mirrors the problem statement:

Break the sentence into words.
Keep only the first k.
Reconstruct the truncated sentence.

For example:

s = "What is the solution to this problem"

After splitting:

["What", "is", "the", "solution", "to", "this", "problem"]

Taking the first four words gives:

["What", "is", "the", "solution"]

Joining them back together produces:

"What is the solution"

This approach is perfectly acceptable for the given constraints. However, it allocates extra memory for all words even though we only need the first k.

Optimal Approach

A more efficient approach is to scan the string character by character and count spaces. Since each space separates words, the position of the kth word can be determined by locating the kth separator.

The key observation is that after encountering k words, we already know exactly where the truncated sentence should end. There is no need to split the entire string into an array.

We iterate through the sentence:

Every time we encounter a space, we know one word has ended.
Once we have seen k words, we return the substring up to that position.

This avoids unnecessary splitting and extra storage.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Splits the entire sentence into words
Optimal	O(n)	O(1)	Scans once and returns substring directly

Algorithm Walkthrough

Optimal Algorithm

Initialize a counter to track how many words have been processed.
Traverse the string character by character using an index.
Every time a space character is encountered, increment the word counter because a word boundary has been reached.
After incrementing the counter, check whether we have already found k words.

If yes, return the substring from the beginning of the string up to the current index.
This substring contains exactly the first k words.

If the loop finishes without returning early, it means the sentence already contains exactly k words, so return the original string.

Why it works

The algorithm relies on the fact that words are separated by exactly one space. Every space marks the end of one word. Therefore, after encountering k - 1 spaces, we know the first k words occupy the substring before the next separator. By returning the substring at the correct boundary, we guarantee that exactly the first k words are included.

Python Solution

class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        word_count = 0

        for index, char in enumerate(s):
            if char == " ":
                word_count += 1

                if word_count == k:
                    return s[:index]

        return s

The implementation uses a single pass through the string.

The variable word_count tracks how many completed words have been encountered. Since spaces separate words, every space increments the count.

During traversal, when the count reaches k, the current index represents the position immediately after the kth word. Returning s[:index] gives the required truncated sentence.

If the loop completes without returning, then the sentence contains exactly k words, so the original string is returned unchanged.

This implementation is concise, efficient, and directly follows the optimal algorithm described earlier.

Go Solution

func truncateSentence(s string, k int) string {
    wordCount := 0

    for i, char := range s {
        if char == ' ' {
            wordCount++

            if wordCount == k {
                return s[:i]
            }
        }
    }

    return s
}

The Go implementation follows the same logic as the Python version.

One important Go-specific detail is that strings are immutable slices of bytes. Returning s[:i] creates a substring efficiently without manually copying characters.

The loop uses range to iterate through characters and indices simultaneously. Since the input contains only English letters and spaces, byte indexing is completely safe here.

There are no concerns about integer overflow because the string length is extremely small.

Worked Examples

Example 1

s = "Hello how are you Contestant"
k = 4

We scan the string and count spaces.

Index	Character	Space Count	Action
5	`' '`	1	First word completed
9	`' '`	2	Second word completed
13	`' '`	3	Third word completed
17	`' '`	4	Return `s[:17]`

Returned substring:

"Hello how are you"

Example 2

s = "What is the solution to this problem"
k = 4

Index	Character	Space Count	Action
4	`' '`	1	First word completed
7	`' '`	2	Second word completed
11	`' '`	3	Third word completed
20	`' '`	4	Return `s[:20]`

Returned substring:

"What is the solution"

Example 3

s = "chopper is not a tanuki"
k = 5

The sentence already contains exactly five words.

Index	Character	Space Count
7	`' '`	1
10	`' '`	2
14	`' '`	3
16	`' '`	4

The loop finishes without reaching a fifth space, so the algorithm returns the original string.

Result:

"chopper is not a tanuki"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is visited at most once
Space	O(1)	Only a few variables are used

The algorithm performs a single linear scan through the sentence. Since each character is processed once, the runtime is proportional to the length of the string.

The space usage is constant because no additional arrays or data structures are allocated. The algorithm only stores counters and indices.

Test Cases

solution = Solution()

# Provided examples
assert solution.truncateSentence("Hello how are you Contestant", 4) == "Hello how are you"  # standard example
assert solution.truncateSentence("What is the solution to this problem", 4) == "What is the solution"  # truncate middle
assert solution.truncateSentence("chopper is not a tanuki", 5) == "chopper is not a tanuki"  # no truncation needed

# Single word sentence
assert solution.truncateSentence("Hello", 1) == "Hello"  # smallest valid sentence

# k equals 1
assert solution.truncateSentence("one two three", 1) == "one"  # keep only first word

# k equals total words
assert solution.truncateSentence("a b c d", 4) == "a b c d"  # return original string

# Short sentence
assert solution.truncateSentence("go fast", 1) == "go"  # truncate short input

# Mixed uppercase and lowercase
assert solution.truncateSentence("Hello WORLD Test", 2) == "Hello WORLD"  # preserve casing

# Longer sentence
assert solution.truncateSentence(
    "this is a longer sentence for testing purposes",
    6
) == "this is a longer sentence for"  # truncation near end

Test	Why
`"Hello how are you Contestant", 4`	Standard truncation case
`"What is the solution to this problem", 4`	Truncation in the middle
`"chopper is not a tanuki", 5`	Sentence already correct length
`"Hello", 1`	Minimum valid input
`"one two three", 1`	Keep only first word
`"a b c d", 4`	No truncation required
`"go fast", 1`	Small sentence handling
`"Hello WORLD Test", 2`	Case sensitivity preservation
Longer testing sentence	Confirms general correctness

Edge Cases

Case 1, `k` equals the total number of words

A common bug is accidentally truncating too early or returning an incomplete sentence when no truncation is actually needed.

For example:

s = "a b c"
k = 3

The implementation handles this correctly because the loop only returns when it encounters the space after the kth word. Since there is no such space, the loop finishes naturally and returns the original string.

Case 2, sentence contains only one word

Single-word input is an important boundary condition because there are no spaces at all.

Example:

s = "Hello"
k = 1

The algorithm never enters the truncation condition because no spaces exist. It simply returns the original string, which is the correct behavior.

Case 3, truncating to exactly one word

When k = 1, the algorithm must stop at the first space.