Leetcode June 10, 2025 -- Problem #3442

 Welcome to my coding blog! I'll mostly be posting about my experiences with Leetcode's daily problems for now, but if any other interesting coding projects come up then I'll definitely post about them here.

I'm posting a day behind on the Leetcode problems, so today's problem is #3442, "Maximum Difference Between Even and Odd Frequency I".

Take a look at the problem, and then we'll get started: https://leetcode.com/problems/maximum-difference-between-even-and-odd-frequency-i/description/

Right away, I can see that this is going to revolve around looping procedures and string indexing. Seems like a job for Python.

My first thought was to create a list of all 26 English characters and iterate through them one by one. However, it occured to me that, by just keeping track of whether a given character has already been analyzed, we can actually use the string itself as a map of all possible characters!
As a bonus, this extends it from working with english letters to any valid character.

Before even writing any code, it's good to have a plan. Here's my first pass at it:

1. Count the number of instances of the first character in the string. Check if it's even or odd.
2. Sort that count into a list depending on whether it's even or odd.
3. Continue doing this for every character in the string.
4. Get the maximum values from the lists of even and odd characters.
5. Return |max(even)-max(odd)|.

While planning my code, I ran into an issue that reminded me how easy it is to let things get out of scope. I realized that, by sorting the quantities into even and odd right away, I had no idea which counts correlated with which characters.
I was midway through adjusting my approach when I realized that the problem doesn't actually care what the letters are!
So, as long as I maintain a list of characters that have already been counted, it really doesn't matter which characters are the max and min. I can just ignore that data when it comes time to do the comparisons.

Finally, before writing any code, I've noticed a slight tweak I need to make. |max(even)-max(odd)| is not the maximum difference. Finding that is a little more complex, but still relatively easy:

1. Take max(even)-min(odd).
2. Take max(odd)-min(even).
3. Return the greater of the two.

Plan in place, I wrote out the code and set up leetcode's two test cases:


def maxDifference(s):
    checked_chars = []
    string_len = len(s)
    odds = []
    evens = []

    for ref_char in s:
        count = 0

        if ref_char in checked_chars:
            continue

        for char in s:
            if char == ref_char:
                count += 1

        if count % 2 == 0:
            evens.append(count)
        else:
            odds.append(count)

    odds.sort(reverse=True)
    evens.sort(reverse=True)

    odd_minus_even = odds[0] - evens[len(evens) - 1]
    even_minus_odd = evens[0] - odds[len(odds) - 1]

    if odd_minus_even > even_minus_odd:
        return odd_minus_even
    else:
        return even_minus_odd
    
print(maxDifference("aaaaabbc"))
print(maxDifference("abcabcab"))


...and that's all it took! I was getting incorrect values at first, but it was simply because I forgot that python's list.sort() method is ascending by default, when I expected it to be descending.
Adding the (reverse=True) argument to both sort statements fixed it.