# Sender With Largest Word Count
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sender-with-largest-word-count)
Canonical: https://scaleengineer.com/dsa/problems/sender-with-largest-word-count
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table, String
---
## Problem
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.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.

# Approaches
## Brute Force by Iterating Through Unique Senders
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.
**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`.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Create a `HashSet` of strings to store unique sender names.
- Iterate through the `senders` array and populate the `HashSet`.
- Initialize `maxCount = -1` and `resultSender = ""`.
- For each `uniqueSender` in the `HashSet`:
    - Initialize `currentCount = 0`.
    - Iterate from `i = 0` to `n-1` (where `n` is the number of messages).
    - If `senders[i]` equals `uniqueSender`:
        - Count the words in `messages[i]` (e.g., by splitting by space).
        - Add the count to `currentCount`.
    - After the inner loop, compare `currentCount` with `maxCount`.
    - If `currentCount > maxCount`, update `maxCount = currentCount` and `resultSender = uniqueSender`.
    - Else if `currentCount == maxCount` and `uniqueSender.compareTo(resultSender) > 0`, update `resultSender = uniqueSender`.
- Return `resultSender`.

## Two-Pass Approach using a HashMap
This approach uses a HashMap to efficiently aggregate the total word count for each sender in a first pass. In a second pass, it iterates through the populated HashMap to find the sender who meets the criteria (largest word count, then lexicographically largest name).
**Time:** `O(M + U * S_len)`, where `M` is the total number of characters in all messages, `U` is the number of unique senders, and `S_len` is the max length of a sender's name. The first pass takes `O(M)` (sum of `split` costs). The second pass takes `O(U * S_len)` for iterating through the map and comparing strings. · **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. The space is dominated by the HashMap storing `U` unique senders.
**Pros:** Much more efficient than the brute-force approach.; Time complexity is linear with respect to the total size of the input.; Clear separation of concerns: first aggregate data, then process it.
**Cons:** Requires two separate passes over the data (one on the input arrays, one on the map).; Uses extra space for the HashMap.
### Explanation
This method improves upon the brute-force approach by avoiding redundant calculations. It uses a `HashMap` to map each sender's name to their cumulative word count.

**Pass 1: Aggregation:** The algorithm iterates through the `messages` and `senders` arrays once. For each message, it counts the words and adds this count to the corresponding sender's total in the HashMap. The `getOrDefault` method is useful here to handle senders encountered for the first time.

**Pass 2: Finding the Maximum:** After the HashMap is fully populated, the algorithm iterates through its entries. It maintains two variables: one for the maximum count found so far (`maxCount`) and one for the corresponding sender's name (`resultSender`). It updates these variables according to the problem's rules: a higher count always wins, and for a tie, the lexicographically larger name wins.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public String largestWordCount(String[] messages, String[] senders) {
        Map<String, Integer> wordCounts = new HashMap<>();
        for (int i = 0; i < messages.length; i++) {
            String sender = senders[i];
            int words = messages[i].split(" ").length;
            wordCounts.put(sender, wordCounts.getOrDefault(sender, 0) + words);
        }

        String resultSender = "";
        int maxCount = 0;
        for (Map.Entry<String, Integer> entry : wordCounts.entrySet()) {
            String sender = entry.getKey();
            int count = entry.getValue();
            if (count > maxCount) {
                maxCount = count;
                resultSender = sender;
            } else if (count == maxCount) {
                if (sender.compareTo(resultSender) > 0) {
                    resultSender = sender;
                }
            }
        }
        return resultSender;
    }
}
```
### Algorithm
- Create a `HashMap<String, Integer>` to store word counts for each sender.
- Iterate from `i = 0` to `n-1`:
    - Get the sender `s = senders[i]` and message `m = messages[i]`.
    - Count the words in `m`. A simple way is `m.split(" ").length`.
    - Update the map: `map.put(s, map.getOrDefault(s, 0) + wordCount)`.
- Initialize `maxCount = -1` and `resultSender = ""`.
- Iterate through each `entry` in the `map.entrySet()`:
    - If `entry.getValue() > maxCount`, update `maxCount = entry.getValue()` and `resultSender = entry.getKey()`.
    - Else if `entry.getValue() == maxCount` and `entry.getKey().compareTo(resultSender) > 0`, update `resultSender = entry.getKey()`.
- Return `resultSender`.

## Optimized Single-Pass Approach with a HashMap
This is the most efficient approach. It combines the aggregation of word counts and the tracking of the "winning" sender into a single pass through the input arrays. As each message is processed, the sender's total count is updated, and the result is immediately compared and potentially updated.
**Time:** `O(M)`, where `M` is the total number of characters in all messages. Each character is visited once for word counting. Map operations and string comparisons happen inside the loop, but their cost is amortized. The total time is dominated by iterating through all characters of all messages. · **Space:** `O(U * S_len)`, where `U` is the number of unique senders and `S_len` is the max length of a sender's name. This space is for the HashMap.
**Pros:** Most time-efficient as it processes the data in a single pass.; Combines logic elegantly, reducing overhead.
**Cons:** The logic inside the loop is slightly more complex than in the two-pass approach.
### Explanation
This approach refines the two-pass method by eliminating the second pass. It maintains the state of the "best sender so far" dynamically within the main loop.

A `HashMap` is still used to store the cumulative word counts for each sender.

The algorithm iterates through the `messages` and `senders` arrays just once. In each iteration, it does the following:
1. Calculates the word count for the current message.
2. Updates the total word count for the current sender in the HashMap.
3. Retrieves the sender's newly updated total count.
4. Compares this new count with the maximum count found so far. If the new count is greater, or if it's equal and the current sender's name is lexicographically larger than the current best, the result is updated on the spot.

By the time the single loop finishes, the algorithm will have found the correct sender.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public String largestWordCount(String[] messages, String[] senders) {
        Map<String, Integer> wordCounts = new HashMap<>();
        String resultSender = "";
        int maxCount = 0;

        for (int i = 0; i < messages.length; i++) {
            String sender = senders[i];
            
            // Since words are separated by a single space, the number of words
            // is the number of spaces plus one.
            int currentWords = 1;
            for (char c : messages[i].toCharArray()) {
                if (c == ' ') {
                    currentWords++;
                }
            }
            
            int newTotalWords = wordCounts.getOrDefault(sender, 0) + currentWords;
            wordCounts.put(sender, newTotalWords);

            if (newTotalWords > maxCount) {
                maxCount = newTotalWords;
                resultSender = sender;
            } else if (newTotalWords == maxCount) {
                if (sender.compareTo(resultSender) > 0) {
                    resultSender = sender;
                }
            }
        }
        return resultSender;
    }
}
```
### Algorithm
- Create a `HashMap<String, Integer>` called `wordCounts`.
- Initialize `resultSender = ""` and `maxCount = 0`.
- Iterate from `i = 0` to `n-1`:
    - Get the sender `s = senders[i]` and message `m = messages[i]`.
    - Count words in `m`.
    - Calculate the new total count for the sender: `newCount = wordCounts.getOrDefault(s, 0) + wordCount`.
    - Update the map: `wordCounts.put(s, newCount)`.
    - Check if the current sender `s` is the new best:
        - If `newCount > maxCount`, update `maxCount = newCount` and `resultSender = s`.
        - Else if `newCount == maxCount` and `s.compareTo(resultSender) > 0`, update `resultSender = s`.
- Return `resultSender`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  string largestWordCount(vector<string> &messages, vector<string> &senders) {
    unordered_map<string, int> cnt;
    int n = senders.size();
    for (int i = 0; i < n; ++i) {
      int v = count(messages[i].begin(), messages[i].end(), ' ') + 1;
      cnt[senders[i]] += v;
    }
    string ans = senders[0];
    for (auto &[sender, v] : cnt) {
      if (cnt[ans] < v || (cnt[ans] == v && ans < sender)) {
        ans = sender;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def largestWordCount(self, messages: List[str], senders: List[str]) -> str: cnt = Counter() for msg, sender in zip(messages, senders): cnt[sender] += msg . count(' ') + 1 ans = '' for sender, v in cnt . items(): if cnt[ans] < v or (cnt[ans] == v and ans < sender): ans = sender return ans

```