Maximum number of words found in sentences

Question

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.

Answer 1

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!).