We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Difference Between Even and Odd Frequency II

Difficulty: Hard

Problem 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 an even frequency in subs.

Return the maximum difference.

Key Insights

  • The substring must have a minimum length of k.
  • We need to identify characters with odd and even frequencies within substrings.
  • The final result is the maximum difference between the frequencies of any two characters that meet the criteria.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case due to checking all substrings. Space Complexity: O(1) as we only need a fixed size frequency array for digits '0' to '4'.

Solution

To solve this problem, we can use a sliding window approach combined with frequency counting. We will iterate through all possible substrings of length at least k, maintaining a frequency count of characters in the current substring. For each substring, we will check the frequencies of all characters to determine which ones have odd and even counts. We will then calculate the differences for valid pairs (odd frequency character and even frequency character) and keep track of the maximum difference found.

Code Solutions

def max_difference(s, k):
    max_diff = float('-inf')
    n = len(s)

    for i in range(n):
        freq = [0] * 5  # Since s contains digits '0' to '4'
        for j in range(i, n):
            freq[int(s[j])] += 1
            if j - i + 1 >= k:  # Ensure substring length is at least k
                odd_freq = None
                even_freq = None
                for num in range(5):
                    if freq[num] % 2 == 1:  # Odd frequency
                        odd_freq = freq[num] if odd_freq is None else max(odd_freq, freq[num])
                    elif freq[num] % 2 == 0 and freq[num] > 0:  # Even frequency
                        even_freq = freq[num] if even_freq is None else max(even_freq, freq[num])
                
                if odd_freq is not None and even_freq is not None:
                    max_diff = max(max_diff, odd_freq - even_freq)

    return max_diff if max_diff != float('-inf') else -1
← Back to All Questions