Skip to content

3442. Maximum Difference Between Even and Odd Frequency I

Description

You are given a string s consisting of lowercase English letters. Your task is to find the maximum difference between the frequency of two characters in the string such that:

  • One of the characters has an even frequency in the string.
  • The other character has an odd frequency in the string.

Return the maximum difference, calculated as the frequency of the character with an odd frequency minus the frequency of the character with an even frequency.

 

Example 1:

Input: s = "aaaaabbc"

Output: 3

Explanation:

  • The character 'a' has an odd frequency of 5, and 'b' has an even frequency of 2.
  • The maximum difference is 5 - 2 = 3.

Example 2:

Input: s = "abcabcab"

Output: 1

Explanation:

  • The character 'a' has an odd frequency of 3, and 'c' has an even frequency of 2.
  • The maximum difference is 3 - 2 = 1.

 

Constraints:

  • 3 <= s.length <= 100
  • s consists only of lowercase English letters.
  • s contains at least one character with an odd frequency and one with an even frequency.

Solutions

Solution 1: Counting

We can use a hash table or an array \(\textit{cnt}\) to record the occurrences of each character in the string \(s\). Then, we traverse \(\textit{cnt}\) to find the maximum frequency \(a\) of characters that appear an odd number of times and the minimum frequency \(b\) of characters that appear an even number of times. Finally, we return \(a - b\).

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(|\Sigma|)\), where \(\Sigma\) is the character set. In this problem, \(|\Sigma| = 26\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int maxDifference(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            ++cnt[c - 'a'];
        }
        int a = 0, b = 1 << 30;
        for (int v : cnt) {
            if (v % 2 == 1) {
                a = Math.max(a, v);
            } else if (v > 0) {
                b = Math.min(b, v);
            }
        }
        return a - b;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxDifference(string s) {
        int cnt[26]{};
        for (char c : s) {
            ++cnt[c - 'a'];
        }
        int a = 0, b = 1 << 30;
        for (int v : cnt) {
            if (v % 2 == 1) {
                a = max(a, v);
            } else if (v > 0) {
                b = min(b, v);
            }
        }
        return a - b;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func maxDifference(s string) int {
    cnt := [26]int{}
    for _, c := range s {
        cnt[c-'a']++
    }
    a, b := 0, 1<<30
    for _, v := range cnt {
        if v%2 == 1 {
            a = max(a, v)
        } else if v > 0 {
            b = min(b, v)
        }
    }
    return a - b
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function maxDifference(s: string): number {
    const cnt: Record<string, number> = {};
    for (const c of s) {
        cnt[c] = (cnt[c] || 0) + 1;
    }
    let [a, b] = [0, Infinity];
    for (const [_, v] of Object.entries(cnt)) {
        if (v % 2 === 1) {
            a = Math.max(a, v);
        } else {
            b = Math.min(b, v);
        }
    }
    return a - b;
}

Comments