# 3445. Maximum Difference Between Even and Odd Frequency II
"""
you are given a string 's' and an integer 'k'. your task is to find the
maximum difference between the frequency of two characters 'freq[a], -
freq[b]', in a substring 'subs' of 's' such that 'subs' has a size of at
least 'k', character 'a' has an odd frequency in 'subs', character 'b' has an
even frequency in 'subs'. return the maximum difference. note that 'subs' can
contain more than 2 distinct characters.
"""
class fenwick_tree:
inf = float("inf")
def __init__(self, n):
self.n = n
self.tree = [self.inf] * (n + 1)
def update(self, i, val):
pos = i + 1
while pos <= self.n:
self.tree[pos] = min(self.tree[pos], val)
pos += pos & -pos
def query(self, i):
res, pos = self.inf, i + 1
while pos > 0:
res = min(res, self.tree[pos])
pos -= pos & -pos
return res
class Solution(object):
def maxDifference(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
n, ans = len(s), float("-inf")
for a in range(5):
for b in range(5):
if a == b:
continue
d = [0] * (n + 1)
pa, pb = [0] * (n + 1), [0] * (n + 1)
cnt_b = [0] * (n + 1)
for i in range(1, n + 1):
digit = int(s[i - 1])
d[i] = (
d[i - 1] + (1 if digit == a else 0) - (1 if digit == b else 0)
)
pa[i] = (pa[i - 1] + (1 if digit == a else 0)) & 1
pb[i] = (pb[i - 1] + (1 if digit == b else 0)) & 1
cnt_b[i] = cnt_b[i - 1] + (1 if digit == b else 0)
trees = [[fenwick_tree(n + 1) for _ in range(2)] for _ in range(2)]
for j in range(n + 1):
if j >= k:
idx = j - k
trees[pa[idx]][pb[idx]].update(cnt_b[idx], d[idx])
if j > 0:
need_p, need_q = (
1 - pa[j],
pb[j],
)
if cnt_b[j] > 0:
best = trees[need_p][need_q].query(cnt_b[j] - 1)
if best != fenwick_tree.inf:
ans = max(ans, d[j] - best)
return ans
if __name__ == "__main__":
obj = Solution()
print(obj.maxDifference(s="12233", k=4))
print(obj.maxDifference(s="1122211", k=3))
print(obj.maxDifference(s="110", k=3))
