#1816

Easy

LeetCode Problem Workspace

Truncate Sentence

Truncate a sentence to contain only the first k words by converting it into an array of words.

Problem Statement

You are given a sentence, which is a string of words separated by spaces. Each word consists of uppercase and lowercase letters only. Your task is to truncate the sentence to only the first k words, where k is provided as an input.

Return the truncated sentence as a string, containing only the first k words from the original sentence.

Examples

Example 1

Input: s = "Hello how are you Contestant", k = 4

Output: "Hello how are you"

The words in s are ["Hello", "how" "are", "you", "Contestant"]. The first 4 words are ["Hello", "how", "are", "you"]. Hence, you should return "Hello how are you".

Example 2

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

Output: "What is the solution"

The words in s are ["What", "is" "the", "solution", "to", "this", "problem"]. The first 4 words are ["What", "is", "the", "solution"]. Hence, you should return "What is the solution".

Example 3

Input: s = "chopper is not a tanuki", k = 5

Output: "chopper is not a tanuki"

Example details omitted.

Constraints

1 <= s.length <= 500
k is in the range [1, the number of words in s].
s consist of only lowercase and uppercase English letters and spaces.
The words in s are separated by a single space.
There are no leading or trailing spaces.

Solution Approach

String to Array Conversion

Start by splitting the input string into an array of words. This is crucial since working with arrays is simpler for truncating and slicing the desired words.

Array Slicing

After converting the string into an array of words, slice the array to keep only the first k words. This ensures that you do not include unnecessary words beyond the specified limit.

Reassemble the Sentence

Finally, join the first k words back into a string using a space separator. This will give you the truncated sentence in the required format.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this approach depends on the operations of splitting and joining the string, which are linear with respect to the length of the input string. Therefore, the overall time complexity is O(n), where n is the length of the string. The space complexity is also O(n), due to the need to store the array of words.

What Interviewers Usually Probe

Candidate should mention splitting the string into an array.
Look for correct array slicing to ensure only the first k words are kept.
Check if the candidate efficiently joins the sliced array back into a string.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the problem and trying to split or slice incorrectly.
Not handling edge cases such as k being equal to the number of words.
Forgetting to join the array back into a string after truncation.

Follow-up variants

Truncate the sentence based on a different separator or delimiter.
Extend the problem to allow truncation to any number of words and sentences.
Handle cases where words are in different languages or character sets.

FAQ

How can I solve the 'Truncate Sentence' problem efficiently?

The most efficient solution involves converting the sentence into an array of words, slicing the array to the first k elements, and joining them back into a string.

What is the time complexity of the 'Truncate Sentence' problem?

The time complexity is O(n), where n is the length of the input string, due to the operations of splitting and joining the string.

How does converting a string to an array help in solving this problem?

Converting the string to an array simplifies truncation, as array slicing allows easy access to the first k words, which is harder to do with a raw string.

What is the space complexity of the solution?

The space complexity is O(n), where n is the length of the string, because we need to store the array of words.

How does this problem relate to common string manipulation techniques?

This problem involves common string manipulation techniques such as splitting, slicing, and joining, which are often used in more complex string-related challenges.

terminal

Solution

Solution 1: Simulation

We traverse the string $s$ from the beginning. For the current character $s[i]$, if it is a space, we decrement $k$. When $k$ becomes $0$, it means that we have extracted $k$ words, so we return the substring $s[0..i)$.

1

2

3

class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        return ' '.join(s.split()[:k])

Solution 2

#### Python3

1

2

3

class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        return ' '.join(s.split()[:k])

Continue Practicing

#1813 sentence similarity iii #1807 evaluate the bracket pairs of a string #1773 count items matching a rule