How do I calculate the difference between even and odd frequencies in a string?

To calculate the difference, build a frequency map of the string, then find the maximum odd frequency and the minimum even frequency. The difference is the absolute difference between these values.

What data structure is useful for this problem?

A hash table (or dictionary) is ideal for building the frequency map and efficiently accessing character counts.

How can I optimize the solution for this problem?

The solution is already optimal with a time complexity of O(n) and space complexity of O(|Σ|), as we only traverse the string once and store a small frequency map.

What if the string contains no even frequencies?

The problem guarantees at least one even and one odd frequency, so this scenario won't happen.

What is the difference between odd and even frequency in this problem?

Odd frequency refers to character counts that are odd numbers, and even frequency refers to character counts that are even numbers. The goal is to find the largest gap between them.

#3442

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

奇偶频次间的最大差值 I

给你一个由小写英文字母组成的字符串 s 。请你找出字符串中两个字符 a 1 和 a 2 的出现频次之间的最大差值 diff = freq(a 1 ) - freq(a 2 ) ，这两个字符需要满足： a 1 在字符串中出现奇数次。 a 2 在字符串中出现偶数次。返回最大差值。示…

哈希表字符串计数

题目描述

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

请你找出字符串中两个字符 a₁ 和 a₂ 的出现频次之间的最大差值 diff = freq(a₁) - freq(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 至少由一个出现奇数次的字符和一个出现偶数次的字符组成。

lightbulb

解题思路

方法一：计数

我们可以用一个哈希表或数组 $\textit{cnt}$ 记录字符串 $s$ 中每个字符的出现次数。然后遍历 $\textit{cnt}$ ，找出出现奇数次的字符的最大频次 $a$ 和出现偶数次的字符的最小频次 $b$ ，最后返回 $a - b$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(|\Sigma|)$ ，其中 $\Sigma$ 是字符集，本题中 $|\Sigma| = 26$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxDifference(self, s: str) -> int:
        cnt = Counter(s)
        a, b = 0, inf
        for v in cnt.values():
            if v % 2:
                a = max(a, v)
            else:
                b = min(b, v)
        return a - b

speed

复杂度分析

指标	值
时间	O(n)
空间	O(

psychology

面试官常问的追问

外企场景

question_mark
Looking for candidates who can efficiently build a frequency map using a hash table.
question_mark
Candidates should demonstrate an understanding of the distinction between odd and even frequencies.
question_mark
Ability to compute the difference between frequencies efficiently is a key signal for success.

warning

常见陷阱

外企场景

error
Candidates may confuse the calculation of maximum odd and minimum even frequencies.
error
Forgetting to check both odd and even frequencies could lead to incorrect results.
error
Candidates might incorrectly handle edge cases where there are multiple odd or even frequencies.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider a variant where the string contains more than one character with the maximum odd frequency.
arrow_right_alt
Another variant could be calculating the difference for substrings of the string.
arrow_right_alt
A variation could involve returning the difference between any odd and any even frequency, not necessarily the maximum odd and minimum even.

help

常见问题

外企场景

继续练习

#3443 K 次修改后的最大曼哈顿距离 #3438 找到字符串中合法的相邻数字 #3389 使字符频率相等的最少操作次数