algoadvance

Leetcode 2114. Maximum Number of Words Found in Sentences

Problem Statement

You are given a list of sentences, where each sentence is a string. Your task is to return the maximum number of words found in any single sentence.

Clarifying Questions

Before we proceed, here are some questions to clarify the problem:

1. Format of Input: Is the input always a list of sentences (strings)?
2. Word Definition: How is a word defined? Are there any special characters or delimiters we need to handle, or is a word simply defined as a sequence of non-space characters?
3. Sentence Constraints: Are there constraints on the length of sentences or the number of sentences?
4. Output Format: Should the output be an integer representing the maximum number of words, or is there some other format required?

Assuming typical constraints and definitions:

• Each sentence is a string of words separated by spaces.
• There are up to (10^4) sentences.
• Each sentence has at most (10^4) characters.

Code

Below is a Java implementation to solve the given problem:

public class Solution {
    public int mostWordsFound(String[] sentences) {
        int maxWords = 0;
        
        for (String sentence : sentences) {
            // Split each sentence by spaces to get words
            String[] words = sentence.split(" ");
            // Update the maximum words count
            maxWords = Math.max(maxWords, words.length);
        }
        
        return maxWords;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        
        String[] sentences = {
            "alice and bob love leetcode",
            "i think so too",
            "this is great thanks very much"
        };
        
        System.out.println(sol.mostWordsFound(sentences));  // Output: 6
    }
}

Strategy

1. Initialization: Declare a variable maxWords to keep track of the maximum number of words found in a sentence.
2. Iterate through Sentences: Loop through each sentence in the input array.
3. Word Count: For each sentence, split the sentence into words using space (" ") as the delimiter.
4. Update Maximum: Update maxWords if the number of words in the current sentence is greater than the previously recorded maximum.
5. Final Result: After the loop completes, return the maxWords.

Time Complexity

• Splitting Each Sentence: Splitting a sentence of (n) characters takes (O(n)) time.
• Total Time Complexity: If there are (m) sentences with combined length (N) characters, the total time complexity is (O(N)). This is because each character is read, split, and counted once.

Space Complexity

• Space for Split Operation: The space used by the .split(" ") method is proportional to the number of words in a sentence, which would be managed by Java’s internal optimizations.
• Overall: The space complexity is (O(N)) for storing the split words temporarily.

This solution efficiently calculates the maximum number of words in any sentence using straightforward string manipulation techniques.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?