Leetcode June 11, 2025 -- Problem #3445

 Today's problem is #3445: Maximum Difference Between Even and Odd Frequency II. https://leetcode.com/problems/maximum-difference-between-even-and-odd-frequency-ii/description/

This builds off of yesterday's problem. Notice, first of all, that the substring *subs* can be any size from k to len(s). At first glance, you might think this means that the largest difference will always come from the largest valid substring where there exists both an even and odd frequency -- I thought the same thing.

However, with a little more thought, we can see that that might not always be true. Take for example, the case s = "1121122". 

The frequency of 1 is 4, and the frequency of 2 is 3, so the maximum difference is 1.

However, look at the substring s[0:5], which is "11211". Here, the frequency of 1 is 4, and the frequency of 2 is 1, so the maximum difference is 3.

The obvious approach is to just run every substring through yesterday's maxDifference function, and then return the largest of the results. This will work, but it's pretty inefficient. Yesterday's function was already O(n^2), but I allowed it because n was sufficiently small, and the average case wasn't actually that bad.

As they say, though, "premature optimization is the root of all evil." So let's do it the inefficient way first, and then see if it even needs optimizing.

Here's my code, with some comments added in:

def maxSubstringDifference(s, k):
    string_len = len(s)
    max_diffs = []


    #input validation -- don't try iterating through an empty range
    if k < string_len:
        #subs_len is the size of the substring
        for subs_len in range(k,string_len):
            pos = 0
            #iterate forward through the string to generate all the substrings of the given size
            while pos+subs_len < string_len:
                difference = maxDifference(s[pos:pos+subs_len])
                max_diffs.append(difference)
                pos += 1

    #the full string is technically also a substring, so we include it
    max_diffs.append(maxDifference(s))

    max_diffs.sort(reverse=True)
    return max_diffs[0]

I also added a special case to yesterday's function to force it to return 0 when no difference can be found. For example, if the string is "112211", then one of the substrings will be "1122", which doesn't have any odd-frequency letters.

As it turns out, this performs well enough and I like the look of this code, so I'm going to leave it as-is for now. If I revisit this again and it proves too slow, then I'll worry about figuring out a faster way, but right now it's pretty much instant.

Here's my full code with one test case.

def maxDifference(s):
    checked_chars = []
    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)

    if len(odds) == 0 or len(evens) == 0:
        return 0

    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
    
def maxSubstringDifference(s, k):
    string_len = len(s)
    max_diffs = []

    if k < string_len:
        for subs_len in range(k,string_len):
            pos = 0
            while pos+subs_len < string_len:
                difference = maxDifference(s[pos:pos+subs_len])
                max_diffs.append(difference)
                pos += 1

    max_diffs.append(maxDifference(s))

    max_diffs.sort(reverse=True)
    return max_diffs[0]


print(maxSubstringDifference("12233", 4))