Sender With Largest Word Count
MedPrompt
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.
Note:
- Uppercase letters come before lowercase letters in lexicographical order.
"Alice"and"alice"are distinct.
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.length1 <= n <= 1041 <= messages[i].length <= 1001 <= senders[i].length <= 10messages[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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach first identifies all unique senders. Then, for each unique sender, it iterates through the entire list of messages to calculate their total word count. It keeps track of the sender with the highest count found so far, handling ties by lexicographical comparison.
Algorithm
- Create a
HashSetof strings to store unique sender names. - Iterate through the
sendersarray and populate theHashSet. - Initialize
maxCount = -1andresultSender = "". - For each
uniqueSenderin theHashSet:- Initialize
currentCount = 0. - Iterate from
i = 0ton-1(wherenis the number of messages). - If
senders[i]equalsuniqueSender:- Count the words in
messages[i](e.g., by splitting by space). - Add the count to
currentCount.
- Count the words in
- After the inner loop, compare
currentCountwithmaxCount. - If
currentCount > maxCount, updatemaxCount = currentCountandresultSender = uniqueSender. - Else if
currentCount == maxCountanduniqueSender.compareTo(resultSender) > 0, updateresultSender = uniqueSender.
- Initialize
- Return
resultSender.
Walkthrough
The algorithm begins by finding all unique sender names. This can be done by iterating through the senders array and adding each name to a HashSet.
It then iterates through each unique sender found in the set.
For every unique sender, it initializes a counter for their total words to zero. It then performs another full iteration through the messages and senders arrays.
During this inner iteration, if the sender of the current message matches the unique sender being processed, it calculates the word count for that message and adds it to the unique sender's total.
After calculating the total word count for a unique sender, it's compared against the current maximum count. If the new count is greater, or if the counts are equal and the current sender's name is lexicographically larger, the result is updated.
This process repeats for all unique senders, ensuring that every message is re-evaluated for each unique sender.
import java.util.HashSet;import java.util.Set; class Solution { public String largestWordCount(String[] messages, String[] senders) { Set<String> uniqueSenders = new HashSet<>(); for (String sender : senders) { uniqueSenders.add(sender); } String resultSender = ""; int maxCount = 0; for (String uniqueSender : uniqueSenders) { int currentCount = 0; for (int i = 0; i < senders.length; i++) { if (senders[i].equals(uniqueSender)) { currentCount += messages[i].split(" ").length; } } if (currentCount > maxCount) { maxCount = currentCount; resultSender = uniqueSender; } else if (currentCount == maxCount) { if (resultSender.isEmpty() || uniqueSender.compareTo(resultSender) > 0) { resultSender = uniqueSender; } } } return resultSender; }}Complexity
Time
`O(U * N * L_avg)`, where `U` is the number of unique senders, `N` is the number of messages, and `L_avg` is the average length of a message. The `split` operation inside the loop contributes the `L_avg` factor. In the worst case, `U` can be close to `N`, leading to a complexity of roughly `O(N^2 * L_avg)`.
Space
`O(U * S_len)`, where `U` is the number of unique senders and `S_len` is the maximum length of a sender's name. This space is used to store the unique senders in a `HashSet`.
Trade-offs
Pros
Conceptually simple to understand.
Does not require complex data structures beyond a set.
Cons
Highly inefficient due to nested loops.
Recalculates word counts repeatedly.
Time complexity is poor, especially for a large number of messages and unique senders.
Solutions
Solution
class Solution {public String largestWordCount(String[] messages, String[] senders) { Map<String, Integer> cnt = new HashMap<>(); int n = senders.length; for (int i = 0; i < n; ++i) { int v = 1; for (int j = 0; j < messages[i].length(); ++j) { if (messages[i].charAt(j) == ' ') { ++v; } } cnt.merge(senders[i], v, Integer : : sum); } String ans = senders[0]; for (var e : cnt.entrySet()) { String sender = e.getKey(); if (cnt.get(ans) < cnt.get(sender) || (cnt.get(ans) == cnt.get(sender) && ans.compareTo(sender) < 0)) { ans = sender; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.