Maximum Difference Between Even and Odd Frequency I
EasyPrompt
You are given a string s consisting of lowercase English letters.
Your task is to find the maximum difference diff = freq(a1) - freq(a2) between the frequency of characters a1 and a2 in the string such that:
a1has an odd frequency in the string.a2has an even frequency in the string.
Return this maximum difference.
Example 1:
Input: s = "aaaaabbc"
Output: 3
Explanation:
- The character
'a'has an odd frequency of5, and'b'has an even frequency of2. - The maximum difference is
5 - 2 = 3.
Example 2:
Input: s = "abcabcab"
Output: 1
Explanation:
- The character
'a'has an odd frequency of3, and'c'has an even frequency of 2. - The maximum difference is
3 - 2 = 1.
Constraints:
3 <= s.length <= 100sconsists only of lowercase English letters.scontains at least one character with an odd frequency and one with an even frequency.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach first calculates the frequency of each character. Then, it separates the characters into two groups: those with odd frequencies and those with even frequencies. Finally, it iterates through all possible pairs of one character from the odd-frequency group and one from the even-frequency group to find the maximum possible difference.
Algorithm
- Create a frequency map (e.g., a
HashMapor an array of size 26) to store the counts of each character in the strings. - Iterate through the string
sto populate the frequency map. - Create two lists:
oddFrequenciesandevenFrequencies. - Iterate through the values in the frequency map. If a frequency is non-zero, add it to the
oddFrequencieslist if it's odd, or to theevenFrequencieslist if it's even. - Initialize a variable
maxDifferenceto a very small number (e.g.,Integer.MIN_VALUE). - Use nested loops to iterate through every frequency
oddFreqinoddFrequenciesand every frequencyevenFreqinevenFrequencies. - For each pair, calculate the difference
oddFreq - evenFreqand updatemaxDifferenceif this difference is larger. - Return
maxDifference.
Walkthrough
To solve the problem, we can start by counting how many times each character appears in the string. A hash map is a suitable data structure for this. After counting, we can segregate the frequencies into two separate lists: one for odd frequencies and one for even frequencies. To find the maximum difference, we need to find an odd frequency a1 and an even frequency a2 such that a1 - a2 is maximized. This is equivalent to finding the largest value in the oddFrequencies list and the smallest value in the evenFrequencies list. This brute-force method checks every possible pair of an odd frequency and an even frequency to find this maximum difference.
import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map; class Solution { public int maxDifference(String s) { Map<Character, Integer> freqMap = new HashMap<>(); for (char c : s.toCharArray()) { freqMap.put(c, freqMap.getOrDefault(c, 0) + 1); } List<Integer> oddFrequencies = new ArrayList<>(); List<Integer> evenFrequencies = new ArrayList<>(); for (int freq : freqMap.values()) { if (freq % 2 != 0) { oddFrequencies.add(freq); } else { evenFrequencies.add(freq); } } int maxDifference = Integer.MIN_VALUE; for (int oddFreq : oddFrequencies) { for (int evenFreq : evenFrequencies) { maxDifference = Math.max(maxDifference, oddFreq - evenFreq); } } return maxDifference; }}Complexity
Time
O(N + K^2), where N is the length of the string and K is the number of unique characters (at most 26). - O(N) to iterate through the string and build the frequency map. - O(K) to populate the odd and even frequency lists. - O(K_odd * K_even) for the nested loops, which is O(K^2) in the worst case. Since K is a constant (26), the overall complexity is dominated by the initial string traversal, making it effectively O(N). However, it's conceptually less efficient due to the nested loops.
Space
O(K), where K is the number of unique characters (at most 26). This space is used for the frequency map and the two lists to store odd and even frequencies. Since K is constant, this is considered O(1) space.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem.
Cons
Less efficient than the optimal approach due to the nested loops that check all pairs of odd and even frequencies, which is unnecessary.
Solutions
Solution
public class Solution { public int MaxDifference(string s) { int[] cnt = new int[26]; foreach(char c in s) { ++cnt[c - 'a']; } int a = 0, b = 1 << 30; foreach(int v in cnt) { if (v % 2 == 1) { a = Math.Max(a, v); } else if (v > 0) { b = Math.Min(b, v); } } return a - b; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.