Find the word that occurs with the highest frequency in a space-separated string, breaking ties by returning the first occurring word.
Problem Statement
<p class="mb-3">Given a string <code>s</code> containing words separated by single spaces, find and return the word that appears with the <strong>maximum frequency</strong>.</p><ul class="list-disc pl-5 space-y-1.5 mt-2"><li>All words consist solely of lowercase English letters.</li><li>If two or more words have the same maximum frequency, return the word that <strong>appears first</strong> in the string.</li></ul>
Examples
Input: s = "apple banana apple orange banana apple"
Output: "apple"
Explanation: 'apple' appears 3 times.
Input: s = "cat dog cat dog parrot"
Output: "cat"
Explanation: Both 'cat' and 'dog' appear 2 times. 'cat' appears first in the string.
Input: s = "code assist consist code consist code"
Output: "code"
Explanation: 'code' appears 3 times.
Constraints
1 <= s.length <= 10^5 s consists of lowercase English letters and single spaces Words are separated by exactly one space with no leading or trailing spaces
Complexity
Time Complexity: O(N)
Space Complexity: O(W)
Hints
- Split the string into individual words using `.split(' ')`.
- Use a Map to track the frequency of each unique word.
- Also record the index of when each word was first seen so you can resolve ties in O(1).
Editorial & Approach
### Method Explanation: Hash Map with First-Seen Tracking
1. **Tokenize**: Split string `s` by space `' '` to obtain an array of words.
2. **Frequency & First-Seen Maps**:
- Iterate through the words array.
- Increment the count in `freq` Map.
- Record the first occurrence index in `firstSeen` Map if the word is new.
3. **Select Winner**:
- Loop through the unique words in `freq`.
- If `count > maxCount`, update `maxCount = count` and `bestWord = word`.
- If `count === maxCount` and `firstSeen.get(word) < firstSeen.get(bestWord)`, update `bestWord = word`.
### Complexity Analysis
- **Time Complexity:** $O(N)$ where $N$ is the total length of string $s$.
- **Space Complexity:** $O(W)$ where $W$ is the number of unique words in the string.