[Leetcode] 3445. Maximum Difference Between Even and Odd Frequency II (retry)

https://leetcode.com/problems/maximum-difference-between-even-and-odd-frequency-ii/description/

initial

absolutely no idea

I got the idea of sliding window but this question is actually crazy. Since digits in s can only be from 0 to 4 inclusiive, we can set a pair of digits in the given substring. Then, we use prefix and parity(odd or even) sum to calculate the count of each 2 digits and the odd/even frequencies of those 2 digits respectively.

Rmb prefix sum formula of prefix_sum[i...j] = prefix_sum[j]-prefix_sum[i-1]? We can use it here.

freq(a) in s[i..j] = count(a,j)-count(a,i-1)
freq(b) in s[i..j] = count(b,j)-count(b,i-1)

to maximise the difference,
count(a,j)-count(a,i-1)-(count(b,j)-count(b,i-1))
= (count(a, j) - count(b, j)) - (count(a, i-1) - count(b, i-1))

that means we needa minimise the RHS.

XOR

But the parity is the hard part here cuz we have to know if this character's frequence count is odd or even. For this we can use XOR operator.

odd - even = odd
even - odd = odd
odd - odd = even
even - even = even

So, for freq[a] to be odd, the parities of count(a, j) and count(a, i-1) must be different. For freq[b] to be even, the parities of count(b, j) and count(b, i-1) must be the same.

Bit 1: count(a) % 2 (1 for odd, 0 for even)
Bit 0: count(b) % 2 (1 for odd, 0 for even)

00 (Decimal 0): count(a) is even, count(b) is even.
01 (Decimal 1): count(a) is even, count(b) is odd.
10 (Decimal 2): count(a) is odd, count(b) is even.
11 (Decimal 3): count(a) is odd, count(b) is odd.
count(a)'s bit is left shifted by 1.

So according to the question, 10 is the right condition that we are looking for.

Magic of XOR for Parity Differences

Now, let's look at how subtraction of parities (or, more precisely, the parity of a difference) relates to XOR.

Think of it like this:

Even + Even = Even (0⊕0=0)
Odd + Odd = Even (1⊕1=0)
Even + Odd = Odd (0⊕1=1)
Odd + Even = Odd (1⊕0=1)
Notice how these "sum of parities" rules are exactly the same as the truth table for the XOR (exclusive OR) operation.

Now, consider subtraction of counts: C_j - C_i. The parity of this difference P(C_j - C_i) depends on the individual parities P(C_j) and P(C_i).

Let P_j be the parity of count(char in S[0...j]) (this is bit 0 state_j for character 'b', or bit 1 state_j for character 'a').
Let P_i be the parity of count(char in S[0...i-1]) (this is bit 0 state_i for character 'b', or bit 1 state_i for character 'a').

Your table shows this relationship perfectly:

P_i (bit 0 state_i) P_j (bit 0 state_j) P_i XOR P_j Parity of count(b) in S[i...j]
0 (even) 0 (even) 0⊕0=0 Even (e.g., 4−2=2)
0 (even) 1 (odd) 0⊕1=1 Odd (e.g., 5−2=3)
1 (odd) 0 (even) 1⊕0=1 Odd (e.g., 4−3=1)
1 (odd) 1 (odd) 1⊕1=0 Even (e.g., 5−3=2)

If statej is the state for prefix s[0, j] and state{i-1} is for prefix s[0, i-1], then:

target_state = state_j ⊕ state_{i-1}
10 = state_j ⊕ state_{i-1}
Therefore, state_{i-1} = state_j ⊕ 10.

This tells us: for a prefix ending at j with state state_j, we must find a previous prefix ending at i-1 that had the state state_j ⊕ 10.

sol (i still dont get 100%)

class Solution:
    def maxDifference(self, s: str, k: int) -> int:
        n = len(s)
        ans = float('-inf')

        # Step 1: Try all (a, b) pairs
        for a in range(5):
            for b in range(5):
                if a == b: continue

                s1 = [0] * (n + 1)
                s2 = [0] * (n + 1)

                # Step 2: Prefix counts
                for i in range(1, n + 1):
                    s1[i] = s1[i - 1] + (int(s[i - 1]) == a)
                    s2[i] = s2[i - 1] + (int(s[i - 1]) == b)

                # Step 3: Track best past difference for each parity
                g = [[float('-inf')] * 2 for _ in range(2)]
                j = 0

                # Step 4: Two-pointer sliding window
                for i in range(k, n + 1):
                    while i - j >= k and s1[i] > s1[j] and s2[i] > s2[j]:
                        pa = s1[j] % 2
                        pb = s2[j] % 2
                        g[pa][pb] = max(g[pa][pb], s2[j] - s1[j])
                        j += 1

                    # Step 5: Check candidate answer
                    pa = s1[i] % 2
                    pb = s2[i] % 2
                    best = g[1 - pa][pb]
                    if best != float('-inf'):
                        ans = max(ans, (s1[i] - s2[i]) + best)

        return -1 if ans == float('-inf') else ans

complexity

n time and space