Truncate Sentence

Easy

Asked by:

4 views

Topics:

Strings

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 <= 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.

Try coding it in LeetCode

Truncate Sentence

Easy

Asked by:

4 views

Topics:

Strings

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 <= 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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s` and the maximum value of `k`?
Can the input string `s` be empty or contain leading/trailing spaces? If so, how should I handle them?
Is `k` guaranteed to be a positive integer? What should I return if `k` is zero or negative?
Are there any punctuation marks or special characters in the string `s`, or will it only contain letters and spaces?
What should I return if the string `s` has fewer than `k` words? Should I return the entire string?

Brute Force Solution

Approach

The brute force approach to truncate a sentence involves examining every possible way to split the sentence. We will check each possible truncated sentence to see if it meets the length requirement. The first k words is the solution.

Here's how the algorithm would work step-by-step:

Start by considering just the first word of the sentence.
Then, consider the first two words.
Next, consider the first three words, and so on, each time adding one more word to the truncated sentence.
Continue this process until you've considered all the words in the sentence.
Stop when you include the required number of words and return that truncated sentence.

Code Implementation

def truncate_sentence_brute_force(input_string, number_of_words):
    words = input_string.split()
    
    #Iterate through the words to truncate the sentence
    for index in range(1, len(words) + 1):
        truncated_words = words[:index]
        
        # Stop truncating once enough words are included
        if len(truncated_words) == number_of_words:

            truncated_sentence = " ".join(truncated_words)

            return truncated_sentence
    #If the string has fewer words than number_of_words
    return input_string

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the sentence, adding one word at a time to the truncated sentence until it reaches the desired number of words, k. In the worst-case scenario, the algorithm iterates through all n words in the sentence if k is equal to n. Therefore, the time complexity is directly proportional to the number of words in the sentence, resulting in O(n) time complexity since it will stop at k (k <= n).

Space Complexity

O(N) – The described algorithm iteratively builds truncated sentences by adding one word at a time. In the worst case, it might construct up to N truncated sentences, where N is the total number of words in the input sentence. Each truncated sentence is stored as a string, potentially requiring storage proportional to the number of characters in that truncated sentence, up to the length of the original sentence. Therefore, in the worst case, the space used to store these temporary truncated sentences grows linearly with the number of words N, leading to a space complexity of O(N).

Optimal Solution

Approach

To solve this problem efficiently, we count words until we reach the desired count. Then we take only the necessary number of words from the beginning. This avoids unnecessary operations on the whole input sentence.

Here's how the algorithm would work step-by-step:

Start from the beginning of the sentence.
Keep track of how many words you've seen so far.
When you reach the target number of words, stop counting.
Take the words you counted and combine them into a new sentence.
Return this new sentence.

Code Implementation

def truncate_sentence(input_sentence, words_to_keep):
    words = input_sentence.split()
    number_of_words_seen = 0
    truncated_words = []

    for word in words:
        # Break when target word count is reached.
        if number_of_words_seen == words_to_keep:
            break

        truncated_words.append(word)
        number_of_words_seen += 1

    # Join the collected words to form the truncated sentence.
    truncated_sentence = " ".join(truncated_words)

    return truncated_sentence

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input sentence of size n (where n represents the length of the sentence in characters) once to count words until the target word count 'k' is reached. After finding the 'k' words, a substring is extracted from the original string. Both the counting of words and extraction of the substring will take at most n steps. Thus, the time complexity is O(n).

Space Complexity

O(k) – The dominant space usage comes from creating a new string composed of the first k words of the input sentence. Specifically, step 4 describes combining the counted words into a new sentence. Therefore, the auxiliary space required to store this new sentence grows linearly with k, where k is the target number of words. No other significant data structures are used; the word count and loop variable use constant space. Thus the auxiliary space complexity is O(k).

Edge Cases

Case	How to Handle
Null or empty string input for the sentence	Return an empty string immediately as there's nothing to truncate.
k is zero or negative	Return an empty string, or the whole sentence if the problem statement specifies that an empty string is the behavior when `k` is less than 1.
k is greater than or equal to the number of words in the sentence	Return the entire original sentence as no truncation is necessary.
Sentence contains only spaces	Return an empty string as there are no actual words.
Sentence starts with leading spaces	Trim the leading spaces before processing to accurately count words.
Sentence contains multiple spaces between words	Handle multiple spaces correctly, treating each sequence of non-space characters as a single word.
Very long sentence (performance considerations)	Iterative approach avoids stack overflow issues for very long sentences, ensuring scalability.
k is a very large number (integer overflow)	No integer overflow is expected because k is an integer representing the number of words to truncate, and this operation is bounded by the number of words in sentence.