easyStringsPattern: Frequency Hash
First Odd Frequency Character Solution
Problem Statement
Given a string s consisting of lowercase English letters, find and return the first character in the string (when traversing from left to right) that has an odd frequency of occurrence in the entire string. If every character in the string occurs an even number of times, return the character '#'.
Examples
Example 1:
Input:s = "revere"
Output:"e"
Explanation: The frequencies of characters in 'revere' are: 'r' occurs 2 times (even), 'e' occurs 3 times (odd), and 'v' occurs 1 time (odd). Traversing from left to right, the first character we encounter with an odd frequency is 'e'.
Example 2:
Input:s = "noon"
Output:"#"
Explanation: The frequencies of characters in 'noon' are: 'n' occurs 2 times (even) and 'o' occurs 2 times (even). Since no characters have an odd frequency, we return '#'.
Constraints
- 1 <= s.length <= 10^5
- s consists only of lowercase English letters.
Time: O(n) Space: O(1)
First, perform a single pass to store character frequencies in a hash map or an array of size 26. Then, iterate through the string again and return the first character whose frequency in the map is odd.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.