{x}
blog image

Maximum Number of Words Found in Sentences

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 Explanation: Finding the Maximum Number of Words in Sentences

This problem involves finding the sentence with the maximum number of words from a given array of strings. The solution leverages the observation that the number of words in a sentence is directly related to the number of spaces present.

Approach:

The most efficient approach involves iterating through each sentence in the input array and counting the spaces within each sentence. Since words are separated by single spaces, the number of words is simply one more than the count of spaces. We keep track of the maximum word count encountered so far and return this value.

Time Complexity Analysis:

The algorithm iterates through each sentence once. The time spent counting spaces in a sentence is proportional to the length of the sentence. Therefore, the overall time complexity is O(L), where L is the total number of characters across all sentences in the input array. This is a linear time complexity.

Space Complexity Analysis:

The algorithm uses a constant amount of extra space to store variables like the current maximum word count. Therefore, the space complexity is O(1), which is constant space complexity.

Code Implementation (Python):

class Solution:
    def mostWordsFound(self, sentences: List[str]) -> int:
        max_words = 0  # Initialize the maximum word count to 0
        for sentence in sentences:
            word_count = sentence.count(' ') + 1 # Count spaces and add 1 for the last word
            max_words = max(max_words, word_count) # Update max_words if a sentence with more words is found
        return max_words

Code Implementation (Java):

class Solution {
    public int mostWordsFound(String[] sentences) {
        int maxWords = 0; // Initialize the maximum word count to 0
        for (String sentence : sentences) {
            int wordCount = sentence.split(" ").length; //split the sentence by spaces and get the length of the array which gives the number of words
            maxWords = Math.max(maxWords, wordCount); // Update maxWords if a sentence with more words is found
        }
        return maxWords;
    }
}

Code Implementation (C++):

class Solution {
public:
    int mostWordsFound(vector<string>& sentences) {
        int max_words = 0; // Initialize the maximum word count to 0
        for (const string& sentence : sentences) {
            int word_count = 0;
            stringstream ss(sentence); // Create a string stream for easier word counting
            string word;
            while (ss >> word) { // Extract words one by one
                word_count++;
            }
            max_words = max(max_words, word_count); // Update max_words if a sentence with more words is found
        }
        return max_words;
    }
};

Code Implementation (JavaScript):

/**
 * @param {string[]} sentences
 * @return {number}
 */
var mostWordsFound = function(sentences) {
    let maxWords = 0; // Initialize the maximum word count to 0
    for (let sentence of sentences) {
        let wordCount = sentence.split(" ").length; //split the sentence by spaces and get the length of the array which gives the number of words
        maxWords = Math.max(maxWords, wordCount); // Update maxWords if a sentence with more words is found
    }
    return maxWords;
};

These implementations all follow the same basic approach, differing only in syntax and specific library functions used for string manipulation. They all achieve the optimal time and space complexity described above.