Easy

题目描述

给你一个由小写英文字母组成的字符串 s。

你的任务是找到字符 a1 和 a2 在字符串中频率的最大差值 diff = freq(a1) - freq(a2)，满足以下条件：

  • a1 在字符串中的频率是奇数。
  • a2 在字符串中的频率是偶数。

返回这个最大差值。

示例 1：

输入：s = "aaaaabbc"
输出：3
解释：
字符 'a' 的频率为 5（奇数），字符 'b' 的频率为 2（偶数）。
最大差值是 5 - 2 = 3。

示例 2：

输入：s = "abcabcab"
输出：1
解释：
字符 'a' 的频率为 3（奇数），字符 'c' 的频率为 2（偶数）。
最大差值是 3 - 2 = 1。

约束条件：

  • 3 <= s.length <= 100
  • s 只包含小写英文字母
  • s 至少包含一个奇数频率的字符和一个偶数频率的字符

提示： 使用频率映射来识别最大奇数频率和最小偶数频率，然后计算它们的差值。

解题思路

解题思路

这是一道字符频率统计的题目。根据题意，我们需要找到频率为奇数的字符中频率最大的，以及频率为偶数的字符中频率最小的，然后计算它们的差值。

算法步骤：

  1. 统计频率：遍历字符串，使用哈希表统计每个字符的出现频率
  2. 分类筛选：将字符按频率的奇偶性分为两组
    • 奇数频率组：找出最大频率值
    • 偶数频率组：找出最小频率值
  3. 计算差值：返回最大奇数频率 - 最小偶数频率

算法优化：

可以在统计频率的同时就进行奇偶性判断和最值更新，避免二次遍历，提高效率。

时间复杂度为 O(n)，空间复杂度为 O(1)（最多26个小写字母）。

代码实现

class Solution {
public:
    int maxDifference(string s) {
        unordered_map<char, int> freq;
        
        // 统计每个字符的频率
        for (char c : s) {
            freq[c]++;
        }
        
        int maxOdd = -1, minEven = INT_MAX;
        
        // 遍历频率映射，找到最大奇数频率和最小偶数频率
        for (auto& p : freq) {
            int count = p.second;
            if (count % 2 == 1) {  // 奇数频率
                maxOdd = max(maxOdd, count);
            } else {  // 偶数频率
                minEven = min(minEven, count);
            }
        }
        
        return maxOdd - minEven;
    }
};

class Solution:
    def maxDifference(self, s: str) -> int:
        from collections import Counter
        
        # 统计每个字符的频率
        freq = Counter(s)
        
        max_odd = -1
        min_even = float('inf')
        
        # 遍历频率，找到最大奇数频率和最小偶数频率
        for count in freq.values():
            if count % 2 == 1:  # 奇数频率
                max_odd = max(max_odd, count)
            else:  # 偶数频率
                min_even = min(min_even, count)
        
        return max_odd - min_even

public class Solution {
    public int MaxDifference(string s) {
        Dictionary<char, int> freq = new Dictionary<char, int>();
        
        // 统计每个字符的频率
        foreach (char c in s) {
            if (freq.ContainsKey(c)) {
                freq[c]++;
            } else {
                freq[c] = 1;
            }
        }
        
        int maxOdd = -1, minEven = int.MaxValue;
        
        // 遍历频率映射，找到最大奇数频率和最小偶数频率
        foreach (var pair in freq) {
            int count = pair.Value;
            if (count % 2 == 1) {  // 奇数频率
                maxOdd = Math.Max(maxOdd, count);
            } else {  // 偶数频率
                minEven = Math.Min(minEven, count);
            }
        }
        
        return maxOdd - minEven;
    }
}

var maxDifference = function(s) {
    const freq = {};
    for (let char of s) {
        freq[char] = (freq[char] || 0) + 1;
    }
    
    let maxOdd = 0;
    let minEven = Infinity;
    
    for (let count of Object.values(freq)) {
        if (count % 2 === 1) {
            maxOdd = Math.max(maxOdd, count);
        } else {
            minEven = Math.min(minEven, count);
        }
    }
    
    return maxOdd - minEven;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)其中 n 是字符串长度，需要遍历字符串一次统计频率，再遍历频率映射一次
空间复杂度O(1)哈希表最多存储 26 个小写英文字母，为常数空间