First Odd Frequency Character — Problem Statement & Solution Guide
Problem Description
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
Input
aabbc
Output
#
Explanation: Step-by-step: with input 'aabbc', we count the frequency of each character. 'a' appears twice, 'b' appears twice, and 'c' appears once. Since all characters have even frequencies, we return '#'.
Input
aabbcc
Output
#
Explanation: Step-by-step: with input 'aabbcc', we count the frequency of each character. 'a' appears twice, 'b' appears twice, and 'c' appears twice. Since all characters have even frequencies, we return '#'.
Constraints
- 1 <= s.length <= 10^5
- s consists only of lowercase English letters.
Optimal Approach & Strategy
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.
Brute Force Approach
For each character in the string, traverse the entire string again to count its occurrences. If the count is odd, return that character immediately; if no such character exists after checking all, return '#'.
Verified Code Solutions
class Solution {
public char firstOddFrequencyCharacter(String s) {
int[] charCount = new int[26];
for (char c : s.toCharArray()) {
charCount[c - 'a']++;
}
for (char c : s.toCharArray()) {
if (charCount[c - 'a'] % 2 != 0) {
return c;
}
}
return '#';
}
}def first_odd_frequency_character(s):
char_count = {}
for char in s:
if char in char_count:
char_count[char] += 1
else:
char_count[char] = 1
for char in s:
if char_count[char] % 2 != 0:
return char
return '#'Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.