Today I have done leetcode's June LeetCoding Challenge with cpp.

June LeetCoding Challenge 11

Description

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.

Example 1:

Example 2:

Example 3:

Constraints:

• 3 <= s.length <= 3 * 104
• s consists only of digits '0' to '4'.
• The input is generated that at least one substring has a character with an even frequency and a character with an odd frequency.
• 1 <= k <= s.length

Solution

class Solution {
public:
  int maxDifference(string s, int k) {
    int len = s.length();
    int answer = INT_MIN;

    for(int a = 0; a < 5; ++a) {
      for(int b = 0; b < 5; ++b) {
        if(a == b) continue;

        vector<int> prefixA(len + 1);
        vector<int> prefixB(len + 1);
        for(int i = 0; i < len; ++i) {
          prefixA[i + 1] = prefixA[i] + (s[i] == a + '0');
          prefixB[i + 1] = prefixB[i] + (s[i] == b + '0');
        }

        int maxParityAB[2][2] = {{INT_MIN, INT_MIN}, {INT_MIN, INT_MIN}};
        int begin = 0;
        for(int end = k; end <= len; ++end) {
          while(end - begin >= k && prefixA[end] > prefixA[begin] && prefixB[end] > prefixB[begin]) {
            int parityA = prefixA[begin] % 2;
            int parityB = prefixB[begin] % 2;

            maxParityAB[parityA][parityB] = max(maxParityAB[parityA][parityB], prefixB[begin] - prefixA[begin]);
            begin += 1;
          }

          int parityA = prefixA[end] % 2;
          int parityB = prefixB[end] % 2;
          int need = maxParityAB[1 - parityA][parityB];

          if(need != INT_MIN) {
            answer = max(answer, prefixA[end] - prefixB[end] + need);
          }
        }
      }
    }

    if(answer == INT_MIN) answer = -1;
    return answer;
  }
};

// Accepted
// 690/690 cases passed (101 ms)
// Your runtime beats 64.1 % of cpp submissions
// Your memory usage beats 56.41 % of cpp submissions (72.2 MB)