# Maximum number of words found in sentences

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
Input: sentences = ["alice and bob love leetcode", "i think so too", "this is great thanks very much"]
Output: 6
Explanation: The first sentence has 5 words, second sentence has 4 words, third sentence has 6 words, so the maximum number of words is 6.

My program:

int mostWordsFound(vector<string>& sentences) {
int n = sentences.size();
int max = 0;

for (int i = 0; i < n; i++) {
int counter = 0;
for (int j = 0; j < sentences[i].size(); j++) {
if (sentences[i][j] == ' ') counter++;
}
if (max < counter) max = counter;
}
return max + 1;
}


My program's output is correct, but the time complexity is O(n^2), are there any other ways to improve this program? Thanks.

• You are assuming words are separated by a single space. Maybe all the test data is; but I would not assume that about real world data. Also you have not considered punctuation will that effect words? 18 hours ago

# Time Complexity

First of all, your time complexity is not O(n^2). You only have one loop going from 0 to n and then loop over each character. So your time complexity rather looks like O(n*k). I don't think it can be any faster, since you need to check every string and every character.

# Using namespace std

I think it's really terrible that leetcode does this by default. Read this link on why it's considered bad practice.

# ref vs const ref

You're taking the array as a ref, but not as a const ref. Since you're not altering it in any way, you should take it as a const ref.

# .size() does not return an int

int n = sentences.size();


the return type of std::vector::size() is std::size_t. Converting it to an int might narrow it (for long vectors) and the size can never be negative anyway.

# Use range-based for loops

You do not even need to store the size, just use range based for loops:

#include <string>
#include <vector>

int mostWordsFound(std::vector<std::string> const& sentences) {
int max = 0;

for( auto const& sentence : sentences ){
int counter{0};
for( auto const& character : sentence ){
if( character == ' '){
counter++;
}
}
max = counter > max? counter : max;
}
return max+1;
}


# A Bug?

You are assuming that the input somehow makes sense. But consider the following code:

int main(){
std::cout << mostWordsFound({"Hello World!", "Hello    World\n"}) << "\n";
}


This will output 5, because of all the consecutive whitespaces. A way to improve this program would be to check, if the previous character was a whitespace also, and then not count the current whitespace. Also, trailing or leading whitespaces will give a wrong result (or imagine a string of only spaces!).

• In the for loop, why did you use the const& keyword after auto ?
– user
Jul 28 at 17:05
• If you do not use it, each loop iteration will create a copy. You can also drop the const and just use a ref, if you want to alter elements while iterating. Jul 28 at 17:09
• I think altering elements while iterating is not possible according to this link: stackoverflow.com/questions/6438086/…
– user
Jul 28 at 17:13
• You understood it wrong. You can alter the elements, but you can not / should not erase or add elements while iterating. See this example here Jul 28 at 17:19