当前位置：首页 > news >正文

LeetCode 3442.奇偶频次间的最大差值 I：计数

news 2025/6/12 22:00:04

【LetMeFly】3442.奇偶频次间的最大差值 I：计数

力扣题目链接：https://leetcode.cn/problems/maximum-difference-between-even-and-odd-frequency-i/

给你一个由小写英文字母组成的字符串 s 。请你找出字符串中两个字符的出现频次之间的最大差值，这两个字符需要满足：

一个字符在字符串中出现 偶数次 。
另一个字符在字符串中出现 奇数次 。

返回最大差值，计算方法是出现 奇数次 字符的次数减去出现 偶数次 字符的次数。

示例 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 至少由一个出现奇数次的字符和一个出现偶数次的字符组成。

解题方法：计数

遍历一遍字符串，统计出每种字符的出现次数。

遍历英文单词的每种字符：

若这种字符出现次数为奇数次，则更新a1的值
否则若这种字符出现次数大于0，则更新a2的值

最终返回 $a_1-a_2$ 。

时间复杂度 $O (l e n (s) + C)$ ，其中 $C = 26$
空间复杂度 $O (C)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-06-10 23:07:14* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-06-10 23:14:08*/
class Solution {
public:int maxDifference(string s) {int cnt[26] = {0};for (char c : s) {cnt[c - 'a']++;}int a1 = 0, a2 = 100;for (int c : cnt) {if (c % 2) {a1 = max(a1, c);} else if (c) {a2 = min(a2, c);}}return a1 - a2;}
};

Python

'''
Author: LetMeFly
Date: 2025-06-10 23:07:14
LastEditors: LetMeFly.xyz
LastEditTime: 2025-06-10 23:18:45
'''
from collections import Counterclass Solution:def maxDifference(self, s: str) -> int:cnt = Counter(s)return max(v for v in cnt.values() if v % 2) - min(v for v in cnt.values() if v % 2 == 0)

Java

/** @Author: LetMeFly* @Date: 2025-06-10 23:07:14* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-06-10 23:40:04*/
class Solution {public int maxDifference(String s) {int[] cnt = new int[26];for (char c : s.toCharArray()) {cnt[c - 'a']++;}int a1 = 0, a2 = 100;for (int t : cnt) {if (t % 2 == 1) {a1 = Math.max(a1, t);} else if (t > 0) {a2 = Math.min(a2, t);}}return a1 - a2;}
}

Go

/** @Author: LetMeFly* @Date: 2025-06-10 23:07:14* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-06-10 23:20:56*/
package mainfunc maxDifference(s string) int {cnt := [26]int{}for _, c := range s {cnt[c - 'a']++}a1, a2 := 0, 100for _, t := range cnt {if t % 2 == 1 {a1 = max(a1, t)} else if t > 0 {a2 = min(a2, t)}}return a1 - a2
}