Skip to main content

Sender With Largest Word Count

Problem Statement​

In this tutorial, we will solve the Sender With Largest Word Count problem. We will provide the implementation of the solution in Python, Java, and C++.

Problem Description​

You have a chat log of n messages. You are given two string arrays messages and senders where messages[i] is a message sent by senders[i].

A message is list of words that are separated by a single space with no leading or trailing spaces. The word count of a sender is the total number of words sent by the sender. Note that a sender may send more than one message.

Return the sender with the largest word count. If there is more than one sender with the largest word count, return the one with the lexicographically largest name.

Examples​

Example 1: Input: messages = ["Hello userTwooo", "Hi userThree", "Wonderful day Alice", "Nice day userThree"], senders = ["Alice", "userTwo", "userThree", "Alice"] Output: "Alice" Explanation: Alice sends a total of 2 + 3 = 5 words. userTwo sends a total of 2 words. userThree sends a total of 3 words. Since Alice has the largest word count, we return "Alice". Example 2: Input: messages = ["How is leetcode for everyone","Leetcode is useful for practice"], senders = ["Bob","Charlie"] Output: "Charlie" Explanation: Bob sends a total of 5 words. Charlie sends a total of 5 words. Since there is a tie for the largest word count, we return the sender with the lexicographically larger name, Charlie.

Constraints​

  • n == messages.length == senders.length
  • 1 <= n <= 104
  • 1 <= messages[i].length <= 100
  • 1 <= senders[i].length <= 10
  • messages[i] consists of uppercase and lowercase English letters and ' '.
  • All the words in messages[i] are separated by a single space.
  • messages[i] does not have leading or trailing spaces.
  • senders[i] consists of uppercase and lowercase English letters only.

Solution of Given Problem​

Intuition and Approach​

The problem can be solved using a brute force approach or an optimized Technique.

Approach 1:Brute Force (Naive)​

Count Words for Each Sender:

Iterate through the messages array. For each message, count the number of words and add this count to the corresponding sender's total in a dictionary. Determine the Sender with the Largest Word Count:

Traverse the dictionary to find the sender with the maximum word count. In case of a tie, choose the sender with the lexicographically larger name.

Codes in Different Languages​

Written by @AmruthaPariprolu
#include <iostream>
#include <vector>
#include <unordered_map>
#include <sstream>
#include <algorithm>

std::string largestWordCount(std::vector<std::string>& messages, std::vector<std::string>& senders) {
    std::unordered_map<std::string, int> wordCount;

    for (int i = 0; i < messages.size(); i++) {
        std::istringstream iss(messages[i]);
        int count = 0;
        std::string word;
        while (iss >> word) count++;
        wordCount[senders[i]] += count;
    }

    std::string result;
    int maxCount = 0;

    for (const auto& entry : wordCount) {
        if (entry.second > maxCount || (entry.second == maxCount && entry.first > result)) {
            maxCount = entry.second;
            result = entry.first;
        }
    }

    return result;
}

Complexity Analysis​

  • Time Complexity: O(n+k)O(n+k)
  • where n is the number of messages and k is the number of unique senders.
  • Space Complexity: O(k)O(k)
  • for storing word counts of senders.

Approach 2: Optimized approach​

Optimized Approach: Word Count Calculation: For each message, split the message string and count the words. This step is O(1) in complexity since the maximum length of a message is fixed. Tracking Maximum Word Count and Sender: Keep track of the maximum word count and the sender with that count directly while iterating through the dictionary. This avoids the need for a separate loop to find the maximum.

Code in Different Languages​

Written by @AmruthaPariprolu
#include <iostream>
#include <vector>
#include <unordered_map>
#include <sstream>
#include <algorithm>

std::string largestWordCount(std::vector<std::string>& messages, std::vector<std::string>& senders) {
    std::unordered_map<std::string, int> wordCount;
    std::string result;
    int maxCount = 0;

    for (int i = 0; i < messages.size(); i++) {
        int count = std::count(messages[i].begin(), messages[i].end(), ' ') + 1;
        wordCount[senders[i]] += count;

        if (wordCount[senders[i]] > maxCount || (wordCount[senders[i]] == maxCount && senders[i] > result)) {
            maxCount = wordCount[senders[i]];
            result = senders[i];
        }
    }

    return result;
}




Complexity Analysis​

  • Time Complexity: O(n+k)O(n+k)

  • Space Complexity: O(k)O(k)

  • This approach is efficient and straightforward.

Video Explanation of Given Problem​

Authors:

Loading...