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 = a1 - 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 and 'b' has an even frequency of .
• The maximum difference is 5 - 2 = 3.

Example 2:

Input: s = "abcabcab"

Output: 1

Explanation:

• The character 'a' has an odd frequency of and 'c' has an even frequency of .
• 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: Hash Map

• Time complexity: O(n)
• Space complexity: O(26 -> 1)

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const maxDifference = function (s) {
  const countMap = new Map();
  let maxOddFrequency = Number.MIN_SAFE_INTEGER;
  let minEvenFrequency = Number.MAX_SAFE_INTEGER;

  for (const letter of s) {
    const count = countMap.get(letter) ?? 0;

    countMap.set(letter, count + 1);
  }

  for (const count of countMap.values()) {
    if (count % 2) {
      maxOddFrequency = Math.max(count, maxOddFrequency);
    } else {
      minEvenFrequency = Math.min(count, minEvenFrequency);
    }
  }

  return maxOddFrequency - minEvenFrequency;
};