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

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

article 2025/2/7 3:53:08

给你一个由小写英文字母组成的字符串 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 至少由一个出现奇数次的字符和一个出现偶数次的字符组成。

先遍历一遍字符串s，统计每个字母的出现次数，然后找出出现次数中，最大的奇数和最小的偶数，相减即可。

C++解法：

class Solution {
public:
    int maxDifference(string s) {
        vector<int> letterToNum(26);
        for (char c : s) {
            ++letterToNum[c - 'a'];
        }

        int minEven = numeric_limits<int>::max();
        int maxOdd = 0;
        for (int i = 0; i < 26; ++i) {
            if (!letterToNum[i]) {
                continue;
            }

            if (letterToNum[i] % 2) {
                maxOdd = max(letterToNum[i], maxOdd);
            } else {
                minEven = min(letterToNum[i], minEven);
            }
        }

        return maxOdd - minEven;
    }
};

go解法：

func maxDifference(s string) int {
    var letterToNum [26]int
    for i := 0; i < len(s); i++ {
        letterToNum[s[i] - 'a']++
    }

    maxOdd := 0
    minEven := math.MaxInt
    for _, value := range letterToNum {
        if value == 0 {
            continue
        }

        if value%2 == 1 {
            if value > maxOdd {
                maxOdd = value
            }
        } else {
            if value < minEven {
                minEven = value
            }
        }
    }

    return maxOdd - minEven
}