Find the character with the highest frequency in a string, breaking ties by choosing the lexicographically smallest character.
Problem Statement
<p class="mb-3">Given a string <code>s</code> consisting of lowercase English letters, find and return the character that appears with the <strong>maximum frequency</strong>.</p><p>If multiple characters have the same maximum frequency, return the character that is <strong>lexicographically smallest</strong> (i.e. appears earliest in alphabetical order).</p>
Examples
Input: s = "testsample"
Output: "e"
Explanation: Both 'e' and 's' appear 2 times. 'e' is lexicographically smaller.
Input: s = "output"
Output: "t"
Explanation: 't' appears 2 times, which is the highest frequency.
Input: s = "banana"
Output: "a"
Explanation: 'a' appears 3 times.
Constraints
1 <= s.length <= 10^5 s consists only of lowercase English letters ('a' - 'z')
Complexity
Time Complexity: O(N)
Space Complexity: O(1)
Hints
- Count the frequency of each character using an array of size 26 or a hash map.
- When scanning through the frequencies from 'a' to 'z', update your maximum only when a strictly higher count is found.
- Checking in alphabetical order naturally guarantees lexicographically smallest tie-breaking!
Editorial & Approach
### Method Explanation: Frequency Array
To find the character with maximum frequency:
1. **Count Frequencies**: Create an array of size 26 initialized to 0. Traverse the string `s` and increment the frequency for each character based on `s.charCodeAt(i) - 97`.
2. **Find Maximum with Lexicographical Tie-breaking**:
- Iterate through indices 0 to 25 (corresponding to `'a'` to `'z'`).
- If `count[i] > maxFreq`, update `maxFreq = count[i]` and `maxChar = String.fromCharCode(97 + i)`.
- By iterating in alphabetical order and only updating on strictly greater frequency, any tie is automatically broken by keeping the earlier character!
### Complexity Analysis
- **Time Complexity:** $O(N)$ where $N$ is the length of string $s$.
- **Space Complexity:** $O(1)$ auxiliary space since the alphabet size is constant (26 lowercase English letters).