Problem

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.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4
5

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.

Solution

Method 1 – Frequency Counting and Max Difference

Intuition

The key idea is to count the frequency of each character in the string, then find the highest frequency among characters with odd counts (a1) and the lowest frequency among characters with even counts (a2). The answer is the maximum difference a1 - a2. This works because the problem asks for the largest possible difference between an odd and an even frequency.

Approach

  1. Initialize a frequency array or map to count occurrences of each character.
  2. Iterate through the string and update the frequency count for each character.
  3. Initialize variables to track the maximum odd frequency (max_odd) and minimum even frequency (min_even).
  4. Iterate through the frequency counts:
  • If the frequency is odd and greater than max_odd, update max_odd.
  • If the frequency is even and less than min_even, update min_even.
  1. Return the difference max_odd - min_even.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
   int maxDifference(string s) {
      int freq[26] = {0};
      for (char c : s) freq[c - 'a']++;
      int max_odd = 0, min_even = 101;
      for (int f : freq) {
        if (f == 0) continue;
        if (f % 2 == 1 && f > max_odd) max_odd = f;
        if (f % 2 == 0 && f < min_even) min_even = f;
      }
      return max_odd - min_even;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

type Solution struct{}

func (Solution) maxDifference(s string) int {
   freq := [26]int{}
   for _, c := range s {
      freq[c-'a']++
   }
   maxOdd, minEven := 0, 101
   for _, f := range freq {
      if f == 0 {
        continue
      }
      if f%2 == 1 && f > maxOdd {
        maxOdd = f
      }
      if f%2 == 0 && f < minEven {
        minEven = f
      }
   }
   return maxOdd - minEven
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
   public int maxDifference(String s) {
      int[] freq = new int[26];
      for (char c : s.toCharArray()) freq[c - 'a']++;
      int maxOdd = 0, minEven = 101;
      for (int f : freq) {
        if (f == 0) continue;
        if (f % 2 == 1 && f > maxOdd) maxOdd = f;
        if (f % 2 == 0 && f < minEven) minEven = f;
      }
      return maxOdd - minEven;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
   fun maxDifference(s: String): Int {
      val freq = IntArray(26)
      for (c in s) freq[c - 'a']++
      var maxOdd = 0
      var minEven = 101
      for (f in freq) {
        if (f == 0) continue
        if (f % 2 == 1 && f > maxOdd) maxOdd = f
        if (f % 2 == 0 && f < minEven) minEven = f
      }
      return maxOdd - minEven
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
   def maxDifference(self, s: str) -> int:
      freq: list[int] = [0] * 26
      for c in s:
        freq[ord(c) - ord('a')] += 1
      max_odd: int = 0
      min_even: int = 101
      for f in freq:
        if f == 0:
           continue
        if f % 2 == 1 and f > max_odd:
           max_odd = f
        if f % 2 == 0 and f < min_even:
           min_even = f
      return max_odd - min_even
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
   pub fn max_difference(s: String) -> i32 {
      let mut freq = [0; 26];
      for b in s.bytes() {
        freq[(b - b'a') as usize] += 1;
      }
      let mut max_odd = 0;
      let mut min_even = 101;
      for &f in &freq {
        if f == 0 { continue; }
        if f % 2 == 1 && f > max_odd { max_odd = f; }
        if f % 2 == 0 && f < min_even { min_even = f; }
      }
      max_odd - min_even
   }
}

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the string (counting frequencies and iterating over 26 letters).
  • 🧺 Space complexity: O(1) (fixed-size frequency array).