#3445

Maximum Difference Between Even and Odd Frequency II

hard · 48.7% accepted · 392 likes · top 35%

string · sliding window · enumeration · prefix sum

⊣ practice⊣ open on leetcode ↗

Description

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 a non-zero even frequency in subs.

Return the maximum difference.

Note that subs can contain more than 2 distinct characters.

Solution