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

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\).

Python3JavaC++GoTypeScriptRustC#

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

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

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

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
}

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

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

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