Truncate Sentence
EasyPrompt
A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each of the words consists of only uppercase and lowercase English letters (no punctuation).
- For example,
"Hello World","HELLO", and"hello world hello world"are all sentences.
You are given a sentence s and an integer k. You want to truncate s such that it contains only the first k words. Return s after truncating it.
Example 1:
Input: s = "Hello how are you Contestant", k = 4
Output: "Hello how are you"
Explanation:
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"
Explanation:
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"
Constraints:
1 <= s.length <= 500kis in the range[1, the number of words in s].sconsist of only lowercase and uppercase English letters and spaces.- The words in
sare separated by a single space. - There are no leading or trailing spaces.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach utilizes built-in string manipulation functions to solve the problem. First, the sentence is split into an array of words based on the space delimiter. Then, a new sentence is constructed by taking only the first k words from this array and joining them back together with spaces.
Algorithm
- Split the input string
sinto an array of stringswordsusing the space character as the delimiter. - Create a
StringBuilderto construct the result string. - Loop from
i = 0tok - 1. - In each iteration, append the word
words[i]to theStringBuilder. - If it's not the last word to be added (i.e.,
i < k - 1), append a space character. - After the loop, convert the
StringBuilderto a string and return it.
Walkthrough
The core idea is to break down the problem into two main steps: splitting the sentence and then building the truncated version. Java's String.split(" ") method is perfect for the first step, as it returns an array of words. Once we have this array, we can easily access the first k words. We then use a StringBuilder for efficient string concatenation, iterating k times to append each of the first k words, followed by a space (except for the very last word). Finally, we convert the StringBuilder back to a string.
class Solution { public String truncateSentence(String s, int k) { String[] words = s.split(" "); StringBuilder result = new StringBuilder(); for (int i = 0; i < k; i++) { result.append(words[i]); if (i < k - 1) { result.append(" "); } } return result.toString(); }}Complexity
Time
O(N), where N is the length of the input string `s`. The `split()` operation needs to scan the entire string, which takes O(N) time. Joining the first `k` words takes time proportional to the length of the resulting string, which is also bounded by O(N).
Space
O(N), where N is the length of the input string `s`. The `split()` method creates an array of words, and the total number of characters stored in this array is proportional to N. This is the dominant factor for auxiliary space.
Trade-offs
Pros
The code is highly readable and straightforward, making it easy to understand and maintain.
It leverages standard library functions, which can reduce development time and potential bugs from manual implementation.
Cons
Inefficient in terms of memory usage because it creates an intermediate array to hold all the words of the original sentence.
Can be slower than a direct iteration approach due to the overhead of the
splitoperation and creating a new array and aStringBuilder.
A more efficient approach is to perform a single pass over the input string. We can iterate through the string, keeping a count of the spaces we encounter. When the number of spaces equals k, we have found the point at which to truncate the string. This method avoids the overhead of creating an intermediate array of all the words.
Algorithm
- Initialize a counter for spaces,
spaceCount, to 0. - Iterate through the input string
scharacter by character using an indexi. - Inside the loop, check if the character
s.charAt(i)is a space. - If it is a space, increment
spaceCount. - After incrementing, check if
spaceCounthas reachedk. If it has, it means we have found the end of the k-th word. The desired output is the substring from the beginning of the string up to the current indexi. Returns.substring(0, i). - If the loop completes without
spaceCountreachingk, it means the sentence has exactlykwords (as per the problem constraints). In this case, the entire original stringsis the answer, so returns.
Walkthrough
This approach optimizes for space by avoiding the creation of any significant intermediate data structures. We traverse the string from left to right. We only need one variable, spaceCount, to track how many words we have passed. Each time we see a space, we increment this counter. When spaceCount becomes equal to k, we know that the character right before this space was the end of the k-th word. We can then take the substring from the start of the string up to the index of this k-th space. If we iterate through the whole string and don't find k spaces, it means the total number of words is k, so the original string is the correct output.
class Solution { public String truncateSentence(String s, int k) { int spaceCount = 0; for (int i = 0; i < s.length(); ++i) { if (s.charAt(i) == ' ') { spaceCount++; if (spaceCount == k) { return s.substring(0, i); } } } // This case is reached if the number of words is k. return s; }}Complexity
Time
O(N), where N is the length of the input string `s`. In the worst-case scenario (when `k` is equal to the number of words in `s`), we have to traverse the entire string once.
Space
O(1) auxiliary space. We only use a few variables for the loop index and space counter, regardless of the input string's size. The space for the returned string is not considered auxiliary space.
Trade-offs
Pros
Extremely space-efficient, using only O(1) auxiliary space.
Very time-efficient as it involves a single pass over the string and may terminate early if
kis small.Avoids the overhead of function calls like
splitand the creation of intermediate data structures.
Cons
The logic is slightly more complex to write manually compared to using high-level built-in functions.
Requires careful handling of indices and loop termination conditions to avoid off-by-one errors.
Solutions
Solution
class Solution {public String truncateSentence(String s, int k) { for (int i = 0; i < s.length(); ++i) { if (s.charAt(i) == ' ' && (--k) == 0) { return s.substring(0, i); } } return s; }}/** * @param {string} s * @param {number} k * @return {string} */ var truncateSentence = function (s, k) { for (let i = 0; i < s.length; ++i) { if (s[i] === " " && --k === 0) { return s.slice(0, i); } } return s; };class Solution {public: string truncateSentence(string s, int k) { for (int i = 0; i < s.size(); ++i) { if (s[i] == ' ' && (--k) == 0) { return s.substr(0, i); } } return s; }};class Solution: def truncateSentence( self, s: str, k: int) -> str: return ' ' . join(s . split()[: k])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.