algoadvance

Leetcode 2114. Maximum Number of Words Found in Sentences

Problem Statement

You are given a list of strings sentences where each sentence i consists of words separated by spaces. Your task is to return the maximum number of words that appear in a single sentence.

A sentence is defined as a string of spaces-separated words. For example, the string "This is a sample sentence" has 5 words: “This”, “is”, “a”, “sample”, “sentence”.

Example:

Note:

Clarifying Questions

  1. Spaces Only for Separation: Can we assume that there are no leading, trailing, or multiple consecutive spaces between words?
    • Assumption: Yes, since stated sentences consist of words separated by single spaces.
  2. Empty Sentences: Are there any completely empty sentences in the input array?
    • Assumption: No, because it’s mentioned that each sentence is of length at least 1.

Strategy

  1. Iterate over each sentence in the sentences list.
  2. Split each sentence based on spaces to count the number of words.
  3. Keep a variable to track the maximum number of words found in any sentence.
  4. Return the maximum count.

Code

Here’s a possible implementation in C++:

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>

int mostWordsFound(std::vector<std::string>& sentences) {
    int maxWords = 0;
    
    for(const std::string& sentence : sentences) {
        // Using stringstream to split the sentence into words
        std::stringstream ss(sentence);
        std::string word;
        int wordCount = 0;
        while (ss >> word) {
            wordCount++;
        }
        // Update the maximum words found if the current sentence has more words
        maxWords = std::max(maxWords, wordCount);
    }
    
    return maxWords;
}

// Example usage:
int main() {
    std::vector<std::string> sentences = {"alice and bob love leetcode", "i think so too", "this is great thanks very much"};
    std::cout << "Maximum number of words in a single sentence: " << mostWordsFound(sentences) << std::endl;
    return 0;
}

Time Complexity

Thus, with efficient handling using string streams, the solution is optimized for typical sentence processing scenarios.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI