点击获取AI摘要

3442. 奇偶频次间的最大差值 I E

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

请你找出字符串中两个字符 a₁ 和 a₂ 的出现频次之间的最大差值 diff = a₁ - a₂，这两个字符需要满足：

a₁ 在字符串中出现 奇数次 。
a₂ 在字符串中出现 偶数次 。

返回最大差值。

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

问题分析

给定一个由小写英文字母组成的字符串 $s$ ，需要找出两个字符 $a_1$ , $a_2$ 的出现频次之间的最大差值：

$\text{diff} = \text{freq}(a_1) - \text{freq}(a_2)$

其中，要求：

$a_1$ 在字符串中出现 奇数次；
$a_2$ 在字符串中出现 偶数次。
题目保证字符串中至少存在一个出现奇数次的字符和一个出现偶数次的字符。为求解此问题，需完成以下两部分工作：

频次统计：统计字符串中每个字符的出现次数；
奇偶分类与极值计算：在出现次数为奇数的字符集合和出现次数为偶数的字符集合中，分别找到最大奇次数和最小偶次数，二者之差即为所求的最大值。

算法思路

初始化计数结构
- 因为只涉及小写英文字母，共 26 个字符，可使用长度为 26 的整型数组 cnt 来记录频次，下标 $0$ 对应 'a'$，$1$ 对应 ‘b’$，……， $25$ 对应 `‘z’$。
遍历字符串进行统计
- 对于字符串 $s$ $s$ 中的每个字符 $c$ $c$ ，执行：
  1
  cnt[ord(c) - ord('a')] += 1
- 经过此步骤，cnt[i] 就是对应第 $i$ 个字母在字符串中出现的总次数。
划分奇数次与偶数次并求极值
- 定义两个变量：
  - max_odd 用于记录出现次数为奇数的字符中的最大值，初始化为 $-1$ 。
  - min_even 用于记录出现次数为偶数的字符中的最小值，初始化为正无穷 $\infty$ 。
- 遍历 cnt 数组中的所有非零频次 num：
  - 如果 $num \bmod 2 = 1$ （奇数），则更新：
    $\mathrm{max\_odd} = \max(\mathrm{max\_odd},\, num)$
  - 如果 $num \bmod 2 = 0$ （偶数），则更新：
    $\mathrm{min\_even} = \min(\mathrm{min\_even},\, num)$
- 由于题目保证存在至少一个奇数次和一个偶数次字符，因此遍历结束后 max_odd 与 min_even 必定已被赋值过。
计算并返回最大差值
- 最终结果即为：
  $\mathrm{answer} = \mathrm{max\_odd} - \mathrm{min\_even}.$

时间复杂度

统计频次时，需遍历整个字符串一次，时间复杂度为 $O(n)$ ，其中 $n = |s|$ 。
遍历频次数组（长度固定为 26）为 $O(1)$ （常量级）。
因此整体时间复杂度为

$O(n) + O(1) = O(n).$

代码分解

初始化阶段
1
cnt = [0] * 26
- 建立长度为 26 的整型数组 cnt，用于存储每个字母在字符串中的出现次数。
频次统计阶段
1
2
for ch in s:
cnt[ord(ch) - ord('a')] += 1
- 遍历字符串，累加每个字符对应的下标值。

奇偶分类与极值计算阶段

max_odd = -1
min_even = float('inf')

for num in cnt:
    if num == 0:
        continue
    if num % 2 == 1:
        # 出现次数为奇数
        if num > max_odd:
            max_odd = num
    else:
        # 出现次数为偶数
        if num < min_even:
            min_even = num

代码实现

class Solution:
    def maxDifference(self, s: str) -> int:
        # 1. 初始化计数数组
        cnt = [0] * 26

        # 2. 遍历字符串进行统计
        for ch in s:
            cnt[ord(ch) - ord('a')] += 1

        # 3. 在奇数次与偶数次字符中找极值
        max_odd = -1  # 记录出现次数为奇数的最大值
        min_even = float('inf')  # 记录出现次数为偶数的最小值

        for num in cnt:
            if num == 0:
                continue  # 如果字符未出现，跳过
            if num % 2 == 1:
                # 奇数次
                if num > max_odd:
                    max_odd = num
            else:
                # 偶数次
                if num < min_even:
                    min_even = num

        # 4. 返回最大差值
        return max_odd - min_even