LeetCode 2114 - Maximum Number of Words Found in Sentences

LeetCode Problem 2114

Difficulty: 🟢 Easy
Topics: Array, String

Solution

Problem Understanding

In this problem, we are given an array of strings called sentences. Each string represents a sentence composed of lowercase English words separated by exactly one space. The problem asks us to determine the maximum number of words that appear in any single sentence.

A key detail is how words are separated. The problem guarantees that:

• There are no leading or trailing spaces.
• Words are separated by exactly one space.
• Every sentence contains at least one word.

Because of these guarantees, counting the number of words becomes very straightforward. In a properly formatted sentence, the number of words is always equal to the number of spaces plus one. For example:

• "hello world" contains 1 space, so it has 2 words.
• "this is easy" contains 2 spaces, so it has 3 words.

The input size is very small:

• At most 100 sentences.
• Each sentence length is at most 100 characters.

These constraints tell us that efficiency is not a major concern. Even a relatively simple solution will easily fit within the limits.

An important observation is that we do not need to actually extract or store the words themselves. We only need the count. This allows us to solve the problem efficiently by scanning characters and counting spaces.

There are a few edge cases worth considering:

• A sentence with only one word, such as "hello", contains no spaces, but still counts as one word.
• Multiple sentences may have the same maximum word count.
• The shortest possible input contains a single sentence with a single word.

The problem guarantees valid formatting, so we do not need to handle malformed input such as double spaces or empty strings.

Approaches

Brute Force Approach

A straightforward approach is to split every sentence into words using the space character and then count how many words are produced.

For each sentence:

1. Call split(" ").
2. Count the resulting words.
3. Keep track of the maximum count seen so far.

This works because the problem guarantees that words are separated by single spaces with no leading or trailing spaces. Therefore, splitting by spaces always produces the correct list of words.

Although this solution is completely acceptable for the given constraints, it performs unnecessary work because it allocates additional memory for the array of split words.

Optimal Approach

The key observation is that the number of words in a valid sentence equals the number of spaces plus one.

Instead of splitting the sentence into substrings, we can simply:

1. Count how many spaces appear in the sentence.
2. Add one to get the number of words.
3. Track the maximum value across all sentences.

This avoids creating intermediate arrays and reduces extra memory usage.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(m)	Splits each sentence into words
Optimal	O(n × m)	O(1)	Counts spaces directly without extra storage

Here:

• n is the number of sentences.
• m is the average sentence length.

Algorithm Walkthrough

1. Initialize a variable called max_words to 0. This variable will store the largest word count found so far.
2. Iterate through each sentence in the sentences array.
3. For the current sentence, count how many spaces it contains. Since each space separates two words, the number of words is:

number_of_spaces + 1

4. Compare this word count with max_words. If the current count is larger, update max_words.
5. Continue processing all sentences until the loop finishes.
6. Return max_words as the final answer.

Why it works

The algorithm works because the problem guarantees that every sentence is correctly formatted with single spaces between words and no extra spaces at the beginning or end. Under these conditions, every space represents exactly one separation between words. Therefore, counting spaces and adding one always gives the exact number of words in the sentence.

By checking every sentence and maintaining the maximum count, the algorithm correctly returns the largest number of words found in any sentence.

Python Solution

from typing import List

class Solution:
    def mostWordsFound(self, sentences: List[str]) -> int:
        max_words = 0

        for sentence in sentences:
            word_count = sentence.count(" ") + 1
            max_words = max(max_words, word_count)

        return max_words

The implementation follows the algorithm directly.

The variable max_words stores the best answer found so far. We iterate through each sentence one by one.

For each sentence, the expression:

sentence.count(" ") + 1

counts the number of spaces and converts that into the number of words. Since the input format is guaranteed to be valid, this calculation is always correct.

We then compare the current sentence's word count with the existing maximum using Python's max() function.

Finally, after processing all sentences, we return the maximum value.

Go Solution

import "strings"

func mostWordsFound(sentences []string) int {
    maxWords := 0

    for _, sentence := range sentences {
        wordCount := strings.Count(sentence, " ") + 1

        if wordCount > maxWords {
            maxWords = wordCount
        }
    }

    return maxWords
}

The Go solution is very similar to the Python version. The main difference is that Go uses the strings.Count() function from the standard library to count spaces.

Go does not have Python's built in max() function for integers, so we update the maximum manually using an if statement.

There are no concerns about integer overflow because the maximum sentence length is extremely small.

Worked Examples

Example 1

Input:

["alice and bob love leetcode",
 "i think so too",
 "this is great thanks very much"]

We process each sentence one by one.

Sentence	Spaces	Words	max_words
"alice and bob love leetcode"	4	5	5
"i think so too"	3	4	5
"this is great thanks very much"	5	6	6

Final answer:

6

Example 2

Input:

["please wait",
 "continue to fight",
 "continue to win"]

Sentence	Spaces	Words	max_words
"please wait"	1	2	2
"continue to fight"	2	3	3
"continue to win"	2	3	3

Final answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × m)	Each character in each sentence is scanned once
Space	O(1)	Only a few integer variables are used

The algorithm examines every sentence and counts spaces within it. Since counting spaces requires scanning the sentence characters, the total runtime depends on the total number of characters across all sentences.

The space usage is constant because no additional data structures proportional to the input size are created.

Test Cases

from typing import List

class Solution:
    def mostWordsFound(self, sentences: List[str]) -> int:
        max_words = 0

        for sentence in sentences:
            word_count = sentence.count(" ") + 1
            max_words = max(max_words, word_count)

        return max_words

solution = Solution()

# Provided example 1
assert solution.mostWordsFound([
    "alice and bob love leetcode",
    "i think so too",
    "this is great thanks very much"
]) == 6  # longest sentence has 6 words

# Provided example 2
assert solution.mostWordsFound([
    "please wait",
    "continue to fight",
    "continue to win"
]) == 3  # multiple sentences share maximum

# Single sentence with one word
assert solution.mostWordsFound([
    "hello"
]) == 1  # minimum valid sentence

# Multiple single-word sentences
assert solution.mostWordsFound([
    "a",
    "b",
    "c"
]) == 1  # no spaces anywhere

# Sentences with increasing lengths
assert solution.mostWordsFound([
    "one",
    "one two",
    "one two three",
    "one two three four"
]) == 4  # maximum appears at end

# Maximum appears first
assert solution.mostWordsFound([
    "this sentence has five words",
    "short one",
    "tiny"
]) == 5  # maximum found immediately

# Equal maximum counts
assert solution.mostWordsFound([
    "a b c",
    "d e f",
    "g h i"
]) == 3  # all sentences tied

# Long sentence stress case
assert solution.mostWordsFound([
    "a b c d e f g h i j"
]) == 10  # many words in one sentence

Test Summary

Test	Why
Example 1	Validates standard multi sentence input
Example 2	Confirms ties are handled correctly
Single word sentence	Tests minimum word count
Multiple single word sentences	Ensures zero spaces still means one word
Increasing sentence lengths	Verifies maximum updates correctly
Maximum appears first	Confirms later smaller values do not overwrite
Equal maximum counts	Tests handling of repeated maximums
Long sentence stress case	Verifies counting works for larger inputs

Edge Cases

Sentences With Only One Word

A sentence like "hello" contains no spaces. A naive implementation that only counts spaces might incorrectly return 0. Our implementation avoids this issue by always adding 1 after counting spaces, producing the correct result of 1.

Multiple Sentences Sharing the Maximum

Several sentences may contain the same highest number of words. For example:

["a b c", "d e f"]

Both contain three words. The algorithm correctly handles this because it only tracks the maximum value itself, not which sentence produced it.

Very Small Input Size

The smallest valid input is a single sentence containing one word:

["a"]

This case can expose bugs related to initialization or empty handling. Our implementation initializes max_words to 0, processes the single sentence, computes 0 + 1, and correctly returns 1.