Welcome to Subscribe On Youtube

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 $\mathit{\text{cnt}}$ to record the occurrences of each character in the string $s$. Then, we traverse $\mathit{\text{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(|\mathrm{\Sigma }|)$, where $\mathrm{\Sigma }$ is the character set. In this problem, $|\mathrm{\Sigma }|=26$.

• Java
• C++
• Python
• Go
• TypeScript

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

• 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
  
  

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

All Problems

All Solutions