Maximum Number of Words Found in Sentences
EasyPrompt
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 <= 1001 <= sentences[i].length <= 100sentences[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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through each sentence in the input array. For each sentence, it uses the built-in split() method to divide the sentence into an array of words based on the space delimiter. The length of this resulting array gives the number of words in the sentence. We maintain a variable to keep track of the maximum word count found so far and update it accordingly.
Algorithm
- Initialize a variable
maxWordsto 0. - Loop through each
sentencein thesentencesarray. - Split the current
sentenceby spaces usingsentence.split(" "). - Get the length of the word array, which is the word count.
- Compare this word count with
maxWordsand updatemaxWordsif it's greater. - After the loop, return
maxWords.
Walkthrough
This approach uses the built-in split() method, which is a common way to handle word tokenization. The logic is to iterate through all sentences, and for each one, we split it into words. The number of words is simply the length of the array returned by split(). We keep a running maximum of these counts.
Here is the Java implementation:
class Solution { public int mostWordsFound(String[] sentences) { int maxWords = 0; for (String sentence : sentences) { // Split the sentence by spaces to get an array of words. String[] words = sentence.split(" "); // Update the maximum with the length of the words array. maxWords = Math.max(maxWords, words.length); } return maxWords; }}Complexity
Time
O(N * L), where N is the number of sentences and L is the maximum length of a sentence. We iterate through N sentences, and for each sentence, the `split()` operation takes O(L) time as it needs to scan the entire string.
Space
O(L), where L is the maximum length of a sentence. The `split()` method creates a new array of strings, which can take up space proportional to the length of the sentence.
Trade-offs
Pros
Simple and easy to understand.
Code is very concise and readable due to the use of a high-level built-in function.
Cons
Less efficient in terms of space complexity due to the creation of a temporary array for each sentence.
The
split()method might have higher overhead compared to manual character iteration.
A more optimized approach is to count the number of words without splitting the string. Since words are separated by a single space, the number of words in a sentence is simply the number of spaces plus one. This method avoids the overhead of creating a new array for each sentence, making it more efficient in terms of memory.
Algorithm
- Initialize a variable
maxWordsto 0. - Iterate through each
sentencein thesentencesarray. - For each sentence, initialize a
spaceCountto 0. - Iterate through each character of the current
sentence. - If a character is a space (' '), increment
spaceCount. - Calculate the word count for the sentence as
spaceCount + 1. - Compare this word count with
maxWordsand updatemaxWordsif it's larger. - After iterating through all sentences, return
maxWords.
Walkthrough
This method is an optimization over the split() approach. It avoids creating intermediate arrays, thus saving space. The core idea is based on the problem's constraint that words are separated by a single space. Therefore, counting the spaces and adding one gives the total number of words. This manual counting is often more performant for simple cases like this.
Here is the Java implementation:
class Solution { public int mostWordsFound(String[] sentences) { int maxWords = 0; for (String sentence : sentences) { int currentSpaces = 0; for (int i = 0; i < sentence.length(); i++) { if (sentence.charAt(i) == ' ') { currentSpaces++; } } // Number of words is number of spaces + 1 int currentWords = currentSpaces + 1; maxWords = Math.max(maxWords, currentWords); } return maxWords; }}Complexity
Time
O(N * L), where N is the number of sentences and L is the maximum length of a sentence. We iterate through each character of every sentence once, so the total time is proportional to the total number of characters in the input.
Space
O(1). We only use a few integer variables to store the counts, regardless of the input size. This is much more memory-efficient than the split approach.
Trade-offs
Pros
Highly memory efficient with O(1) space complexity.
Potentially faster in practice due to avoiding the overhead of string splitting and new object/array creation.
Cons
The code is slightly more verbose than the
split()method approach.
Solutions
Solution
class Solution {public int mostWordsFound(String[] sentences) { int ans = 0; for (var s : sentences) { int cnt = 1; for (int i = 0; i < s.length(); ++i) { if (s.charAt(i) == ' ') { ++cnt; } } ans = Math.max(ans, cnt); } return ans; }}class Solution {public: int mostWordsFound(vector<string> &sentences) { int ans = 0; for (auto &s : sentences) { int cnt = 1 + count(s.begin(), s.end(), ' '); ans = max(ans, cnt); } return ans; }};class Solution: def mostWordsFound( self, sentences: List[str]) -> int: return 1 + max(s . count(' ') for s in sentences)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.