Skip to content

3442. Maximum Difference Between Even and Odd Frequency I

SourceWeekly Contest 435 Q1DifficultyEasyRating1220

Description

You are given a string s consisting of lowercase English letters.

Your task is to find the maximum difference diff = freq(a1) - freq(a2) between the frequency of characters a1 and a2 in the string such that:

  • a1 has an odd frequency in the string.
  • a2 has an even frequency in the string.

Return this maximum difference.

 

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

Thinking

We need the largest odd frequency minus the smallest even frequency. A single count over lowercase letters suffices.

The statement is about the whole string, not a substring.

Scan a counter, take the max odd and the min even, and return their difference.

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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
impl Solution {
    pub fn max_difference(s: String) -> i32 {
        let mut cnt = [0; 26];
        for c in s.bytes() {
            cnt[(c - b'a') as usize] += 1;
        }
        let mut a = 0;
        let mut b = 1 << 30;
        for &v in cnt.iter() {
            if v % 2 == 1 {
                a = a.max(v);
            } else if v > 0 {
                b = b.min(v);
            }
        }
        a - b
    }
}

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

Comments