Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Fix the distinct characters a and b. A substring's frequency difference is the difference between two prefix values, countA - countB. Its a count is odd when the endpoint prefix parities differ for a, while its b count is even when their b parities match. This gives four prefix-parity states.

Approach

Try every ordered pair from the five-digit alphabet. Scan right endpoints while maintaining prefix counts through the right endpoint and through a movable left boundary. Before querying an answer, admit left prefixes only when the substring is at least k long and contains at least two b characters. For each admitted parity state, retain the smallest prefix difference.

The required left state is the right state with only the a parity bit flipped. Subtract its best stored difference from the current right-prefix difference and maximize the answer. The two-b admission test excludes zero occurrences, which would otherwise pass an even-parity check. Once a left prefix is eligible, extending the right endpoint keeps its length and b count eligible. Take the maximum over all character pairs, allowing negative answers.

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

        def calc(a, b):
            return ((a & 1) << 1) | (b & 1)
        
        for a in '01234':
            for b in '01234':
                if a == b: continue

                ca, cb = 0, 0
                pa, pb = 0, 0
                best = [float('inf')] * 4

                l = -1
                for r in range(n):
                    if s[r] == a: ca += 1
                    if s[r] == b: cb += 1

                    while r - l >= k and cb - pb >= 2:
                        l_state = calc(pa, pb)
                        best[l_state] = min(best[l_state], pa - pb)
                        l += 1
                        if s[l] == a: pa += 1
                        if s[l] == b: pb += 1
                    
                    r_state = calc(ca, cb)
                    if best[r_state ^ 0b10] != float('inf'):
                        res = max(res, ca - cb - best[r_state ^ 2])
        
        return res

Complexity analysis

Let n = s.length. Time: O(25n) = O(n) because the alphabet is the fixed five digits. Auxiliary space: O(1).