Maximum Number of Words Found in Sentences

Easy

Microsoft

0 views

Topics:

ArraysStrings

A sentence is a list of words that are separated by a single space with no leading or trailing spaces.

You are given an array of strings sentences, where each sentences[i] represents a single sentence.

Return the maximum number of words that appear in a single sentence.

Example 1:

Input: sentences = ["alice and bob love leetcode", "i think so too", "this is great thanks very much"]
Output: 6
Explanation: 
- The first sentence, "alice and bob love leetcode", has 5 words in total.
- The second sentence, "i think so too", has 4 words in total.
- The third sentence, "this is great thanks very much", has 6 words in total.
Thus, the maximum number of words in a single sentence comes from the third sentence, which has 6 words.

Example 2:

Input: sentences = ["please wait", "continue to fight", "continue to win"]
Output: 3
Explanation: It is possible that multiple sentences contain the same number of words. 
In this example, the second and third sentences (underlined) have the same number of words.

Constraints:

1 <= sentences.length <= 100
1 <= sentences[i].length <= 100
sentences[i] consists only of lowercase English letters and ' ' only.
sentences[i] does not have leading or trailing spaces.
All the words in sentences[i] are separated by a single space.

Maximum Number of Words Found in Sentences

Easy

Microsoft

0 views

Topics:

ArraysStrings

A sentence is a list of words that are separated by a single space with no leading or trailing spaces.

You are given an array of strings sentences, where each sentences[i] represents a single sentence.

Return the maximum number of words that appear in a single sentence.

Example 1:

Input: sentences = ["alice and bob love leetcode", "i think so too", "this is great thanks very much"]
Output: 6
Explanation: 
- The first sentence, "alice and bob love leetcode", has 5 words in total.
- The second sentence, "i think so too", has 4 words in total.
- The third sentence, "this is great thanks very much", has 6 words in total.
Thus, the maximum number of words in a single sentence comes from the third sentence, which has 6 words.

Example 2:

Input: sentences = ["please wait", "continue to fight", "continue to win"]
Output: 3
Explanation: It is possible that multiple sentences contain the same number of words. 
In this example, the second and third sentences (underlined) have the same number of words.

Constraints:

1 <= sentences.length <= 100
1 <= sentences[i].length <= 100
sentences[i] consists only of lowercase English letters and ' ' only.
sentences[i] does not have leading or trailing spaces.
All the words in sentences[i] are separated by a single space.

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 number of sentences I should expect in the input array?
Can a sentence be empty or contain leading/trailing spaces?
Are sentences guaranteed to be valid sentences, or could they contain multiple spaces between words or special characters beyond letters and spaces?
How should I handle punctuation marks (e.g., commas, periods) within a sentence? Should they be considered as part of a word or separate words?
What should I return if the input array is empty or null?

Brute Force Solution

Approach

The brute force strategy for this problem is straightforward: we will count the words in each sentence and then compare these counts. Our goal is to find the sentence with the highest number of words by checking every sentence individually.

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

Take the first sentence.
Count how many words are in that sentence.
Remember this number as the current maximum.
Now, take the next sentence.
Count the words in this sentence.
If this new count is bigger than the current maximum, replace the current maximum with this new count.
Keep repeating steps 4 through 6 for all the sentences.
After checking every sentence, the number you remembered as the maximum is the answer.

Code Implementation

def maximum_number_of_words_found_in_sentences(sentences):
    maximum_word_count = 0

    for sentence in sentences:
        # Split the sentence into words using space as the delimiter
        words = sentence.split()

        current_word_count = len(words)

        # Update maximum_word_count if current_word_count is greater
        if current_word_count > maximum_word_count:
            maximum_word_count = current_word_count

    return maximum_word_count

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the number of sentences in the input array and m be the maximum number of words in any single sentence. The algorithm iterates through each of the n sentences. For each sentence, it counts the number of words, which takes O(m) time in the worst case where the sentence has m words. Therefore, the overall time complexity is O(n*m) because we perform an O(m) operation for each of the n sentences. The time complexity is not O(n) because the word counting operation depends on the length of the sentence.

Space Complexity

O(1) – The described algorithm uses a single variable to store the current maximum word count encountered so far. Regardless of the number of sentences or the number of words in any sentence, this is the only extra space needed. Therefore, the auxiliary space used is constant. Thus, the space complexity is O(1).

Optimal Solution

Approach

The goal is to find the sentence with the most words. We need to go through each sentence and count how many words it has. Finally, we return the largest word count we saw during this process.

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

Look at the first sentence.
Count the number of words in that sentence. Words are separated by spaces.
Remember the number of words. If this is the first sentence, this is currently the most words seen so far.
Move on to the next sentence.
Count the words in that sentence.
Compare that count to the largest count seen so far. If the new sentence has more words, replace the 'largest count' with the new count.
Repeat steps 4-6 for every sentence.
Once all sentences have been checked, report the largest word count you remembered. This is the maximum number of words found in any of the sentences.

Code Implementation

def maximum_number_of_words_found_in_sentences(sentences):
    max_words = 0

    for sentence in sentences:
        # Split the sentence into words using spaces as delimiters.
        words = sentence.split()

        number_of_words = len(words)

        # Update the maximum word count if needed.
        if number_of_words > max_words:
            max_words = number_of_words

    # We have now iterated through all sentences.
    return max_words

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each sentence in the input array. For each sentence, it counts the number of words, which is proportional to the length of the sentence. If we let 'n' represent the total number of characters across all sentences, then on average, each of the sentences will be length n/s (where s is the number of sentences). Therefore the work is proportional to n (length of each sentence * number of sentences) which is O(n).

Space Complexity

O(1) – The algorithm iterates through sentences and maintains a variable to store the current sentence's word count and another to store the maximum word count seen so far. These variables use constant extra space, independent of the number of sentences or the length of each sentence. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately, as there are no sentences to process.
Array containing only empty strings	Each empty string will have 0 words, so return 0.
A single sentence in the array	The maximum number of words is simply the number of words in that sentence, so count and return.
Very long sentences (close to maximum string length)	Ensure the word counting logic is efficient and avoids unnecessary memory allocation or string copies, potentially causing memory exhaustion.
Sentences with leading/trailing spaces or multiple spaces between words	Trim leading/trailing spaces and handle multiple spaces between words correctly to count accurate words.
Sentences with punctuation marks (periods, commas, etc.) within words	Define clear rules for how punctuation affects word separation (e.g., treat 'word.' as one word or two).
Sentences containing only spaces	These sentences should be treated as having zero words, and should not cause errors in word counting logic.
Maximum sized input array of very long sentences	The solution's space and time complexity should be considered for large datasets to ensure it doesn't exceed memory limits or take excessive time.