Problem Description

You are given an array of strings called sentences, where each element represents a single sentence. A sentence is defined as a list of words separated by single spaces, with no leading or trailing spaces.

Your task is to find the maximum number of words that appear in any single sentence from the given array.

For example, if you have sentences like:

• "alice and bob love leetcode" (5 words)
• "i think so too" (4 words)
• "this is great thanks very much" (6 words)

The answer would be 6 since the third sentence contains the most words.

The solution cleverly counts the number of spaces in each sentence and adds 1 to get the word count (since the number of words equals the number of spaces plus one). It then returns the maximum value found across all sentences.

Intuition

The key observation is that in a properly formatted sentence (no leading or trailing spaces, single spaces between words), there's a direct relationship between the number of spaces and the number of words.

If we think about how words are separated in a sentence:

• 1 word has 0 spaces: "hello"
• 2 words have 1 space: "hello world"
• 3 words have 2 spaces: "hello world everyone"
• n words have n-1 spaces

This pattern reveals that number of words = number of spaces + 1.

Instead of splitting each sentence into an array of words and counting them (which would require more memory and processing), we can simply count the spaces. This is more efficient because:

1. Counting characters is a simple linear scan through the string
2. We don't need to create any intermediate data structures
3. The built-in count() method is optimized for this operation

So the approach becomes straightforward: for each sentence, count the spaces, add 1 to get the word count, and keep track of the maximum across all sentences. This gives us the answer in a single pass through the data with minimal overhead.

Solution Approach

The solution uses a simple space counting technique to determine the number of words in each sentence.

Implementation Steps:

1. Iterate through all sentences: We need to examine each sentence in the sentences array to find which one has the most words.

2. Count spaces in each sentence: For each sentence s, we use s.count(' ') to count the number of space characters. This built-in string method efficiently counts all occurrences of the space character.

3. Calculate word count: Since words are separated by spaces, the number of words equals the number of spaces plus 1. For example:

   • "hello world" has 1 space → 2 words
   • "a b c d" has 3 spaces → 4 words

4. Find the maximum: We use Python's max() function with a generator expression (s.count(' ') for s in sentences) to find the sentence with the most spaces. The generator expression avoids creating an intermediate list, making it memory-efficient.

5. Return the result: Add 1 to the maximum space count to get the maximum word count.

Complete Solution:

class Solution:
    def mostWordsFound(self, sentences: List[str]) -> int:
        return 1 + max(s.count(' ') for s in sentences)

Time Complexity: O(n × m) where n is the number of sentences and m is the average length of each sentence, as we need to scan through each character of each sentence.

Space Complexity: O(1) as we only use a constant amount of extra space regardless of input size.

Example Walkthrough

Let's walk through a small example with the input: sentences = ["hello world", "leetcode", "the quick brown fox"]

Step 1: Process the first sentence "hello world"

• Count spaces: There is 1 space between "hello" and "world"
• Word count: 1 space + 1 = 2 words
• Current maximum: 2

Step 2: Process the second sentence "leetcode"

• Count spaces: There are 0 spaces (single word)
• Word count: 0 spaces + 1 = 1 word
• Current maximum: remains 2 (since 1 < 2)

Step 3: Process the third sentence "the quick brown fox"

• Count spaces: There are 3 spaces (between "the"-"quick", "quick"-"brown", "brown"-"fox")
• Word count: 3 spaces + 1 = 4 words
• Current maximum: updates to 4 (since 4 > 2)

Step 4: Return the result

• The maximum word count found is 4

Using the one-liner solution: 1 + max(s.count(' ') for s in sentences)

• The generator produces: 1, 0, 3 (space counts for each sentence)
• max(1, 0, 3) = 3
• Final result: 1 + 3 = 4

Therefore, the function returns 4, which is the maximum number of words in any single sentence.

Solution Implementation

Time and Space Complexity

The time complexity is O(L), where L is the total length of all strings in the array sentences. This is because the algorithm needs to traverse through each character in every sentence to count the spaces. The count(' ') method for each string takes time proportional to the length of that string, and we apply this operation to all sentences in the list.

The space complexity is O(1). The algorithm only uses a constant amount of extra space regardless of the input size. The generator expression (s.count(' ') for s in sentences) doesn't create a list but instead generates values one at a time, and the max() function only needs to keep track of the maximum value seen so far, requiring constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Assuming Empty Input Array

The solution will fail if the sentences array is empty because max() cannot operate on an empty sequence.

Example of failure:

sentences = []
# This will raise: ValueError: max() arg is an empty sequence

Solution:

class Solution:
    def mostWordsFound(self, sentences: List[str]) -> int:
        if not sentences:  # Handle empty array
            return 0
        return 1 + max(sentence.count(' ') for sentence in sentences)

2. Multiple Consecutive Spaces

The current solution assumes sentences are well-formatted with single spaces between words. If there are multiple consecutive spaces, the word count will be incorrect.

Example of incorrect behavior:

sentences = ["hello  world"]  # Two spaces between words
# Current solution returns 3 (counting 2 spaces + 1)
# But there are actually only 2 words

Solution:

class Solution:
    def mostWordsFound(self, sentences: List[str]) -> int:
        max_words = 0
        for sentence in sentences:
            # Split handles multiple spaces correctly
            word_count = len(sentence.split())
            max_words = max(max_words, word_count)
        return max_words

3. Leading or Trailing Spaces

Although the problem states there are no leading or trailing spaces, if the input violates this assumption, the count will be off.

Example of incorrect behavior:

sentences = [" hello world "]  # Leading and trailing spaces
# Current solution counts 2 spaces, returns 3
# But there are actually only 2 words

Solution:

class Solution:
    def mostWordsFound(self, sentences: List[str]) -> int:
        return max(len(sentence.strip().split()) for sentence in sentences) if sentences else 0

4. Performance Consideration for Very Long Sentences

While the space-counting approach is efficient, using split() might be more readable and handles edge cases better, with negligible performance difference for typical inputs.

Alternative robust solution:

class Solution:
    def mostWordsFound(self, sentences: List[str]) -> int:
        # More robust: handles multiple spaces, leading/trailing spaces
        return max((len(s.split()) for s in sentences), default=0)