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.
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; }}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.