Watch 4 video solutions for Sender With Largest Word Count, a medium level problem involving Array, Hash Table, String. This walkthrough by Programming Live with Larry has 359 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
"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 ' '.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.Problem Overview: You receive two arrays: messages and senders. Each message belongs to the sender at the same index. The goal is to compute the total number of words sent by each sender and return the sender with the largest cumulative word count. If multiple senders tie, return the lexicographically largest sender name.
Approach 1: Divide and Conquer (O(n·m) time, O(k) space)
Split the messages array into smaller segments and compute word counts for each segment independently. Each subproblem counts words in its portion and aggregates totals in a hash map keyed by sender. During the merge step, combine maps by summing counts for identical senders. Word counting per message can be done by counting spaces and adding one, or by splitting the string. The final pass scans the aggregated map to find the sender with the maximum total, breaking ties using lexicographic comparison.
This approach mirrors classic divide and conquer patterns where large datasets are processed in chunks. It works well when message data is distributed or processed in parallel systems. The dominant cost is iterating through all characters of all messages, giving O(n·m) time where m is average message length, and O(k) space for storing word counts of k unique senders.
Approach 2: Dynamic Programming / Incremental Counting (O(n·m) time, O(k) space)
Process messages sequentially while maintaining a running total of words per sender. Use a hash table where the key is the sender name and the value is the cumulative word count. For each message, compute its word count and immediately update the sender’s total. While updating, track the current best sender by comparing totals and resolving ties using lexicographic order.
This incremental strategy behaves like a lightweight dynamic programming pattern: each state (sender total) builds on previous results instead of recomputing counts. Because every message is processed exactly once and each update is O(1) average time, the full algorithm runs in O(n·m). Space usage remains O(k) for storing totals of unique senders.
Recommended for interviews: The hash table counting approach (Approach 2) is what interviewers expect. It shows you recognize the problem as a frequency aggregation task using HashMap/dict. Mentioning the divide-and-conquer variation demonstrates awareness of scalable data processing, but the single-pass counting solution is the most direct and practical.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer Aggregation | O(n·m) | O(k) | Useful when processing large message datasets in parallel or distributed systems |
| Hash Table Incremental Counting (Dynamic Programming) | O(n·m) | O(k) | Best general solution; single pass with constant-time updates |