Maximum Number of Words Found in Sentences

Difficulty: Easy | Acceptance: 86.70% | Paid: No Topics: Array, String

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

Each word consists of lowercase and uppercase English letters.

Given an array of strings sentences, return the maximum number of words that appear in a single sentence.

• Examples
• Constraints
• Approach 1: Split and Count
• Approach 2: Count Spaces

Examples

Input: sentences = ["alice and bob love leetcode", "i think so too", "this is great thanks very much"]
Output: 6
Explanation: 
- "alice and bob love leetcode" has 5 words.
- "i think so too" has 4 words.
- "this is great thanks very much" has 6 words.
The maximum number of words is 6.

Input: sentences = ["please wait", "continue to fight", "continue to win"]
Output: 3
Explanation: 
- "please wait" has 2 words.
- "continue to fight" has 3 words.
- "continue to win" has 3 words.
The maximum number of words is 3.

Constraints

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

Split and Count

Intuition The most straightforward way to count words in a string is to split the string by the space delimiter and count the resulting elements.

Steps

• Initialize a variable maxWords to 0.
• Iterate through each sentence in the sentences array.
• For each sentence, split the string by the space character ” “.
• The length of the resulting array is the number of words in that sentence.
• Update maxWords if the current sentence has more words.
• Return maxWords.

from typing import List

class Solution:
    def mostWordsFound(self, sentences: List[str]) -> int:
        max_words = 0
        for s in sentences:
            # Split by space and count the elements
            word_count = len(s.split(" "))
            max_words = max(max_words, word_count)
        return max_words

Complexity

• Time: O(N * L) where N is the number of sentences and L is the average length of a sentence.
• Space: O(L) to store the split array for each sentence.
• Notes: This approach is very readable but allocates extra memory for the split arrays.

Count Spaces

Intuition Since words are separated by exactly one space, the number of words in a sentence is equal to the number of spaces plus one. We can simply count the space characters in each string.

Steps

• Initialize a variable maxWords to 0.
• Iterate through each sentence in the sentences array.
• For each sentence, iterate through its characters and count how many spaces (” ”) are present.
• The word count is spaceCount + 1.
• Update maxWords if the current sentence has more words.
• Return maxWords.

from typing import List

class Solution:
    def mostWordsFound(self, sentences: List[str]) -> int:
        max_words = 0
        for s in sentences:
            # Count spaces and add 1 for the word count
            word_count = s.count(" ") + 1
            max_words = max(max_words, word_count)
        return max_words

Complexity

• Time: O(N * L) where N is the number of sentences and L is the average length of a sentence.
• Space: O(1) as we only use a few variables for counting.
• Notes: This is the most optimal approach as it avoids allocating extra memory for string arrays.