3442. Maximum Difference Between Even and Odd Frequency II

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 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:

Input: s = "12233", k = 4

Output: -1

Explanation:

For the substring "12233", the frequency of '1' is 1 and the frequency of '3' is 2. The difference is 1 - 2 = -1.

Example 2:

Input: s = "1122211", k = 3

Output: 1

Explanation:

For the substring "11222", the frequency of '2' is 3 and the frequency of '1' is 2. The difference is 3 - 2 = 1.

Example 3:

Input: s = "110", k = 3

Output: -1

 

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

 

Solutions

Solution: Prefix Sum + Sliding Window

• Time complexity: O(20n -> n)
• Space complexity: O(n+20)

 

JavaScript

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
const maxDifference = function (s, k) {
  const n = s.length;
  const permutations = [];
  let result = Number.MIN_SAFE_INTEGER;

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

      permutations.push([a, b]);
    }
  }

  for (const [a, b] of permutations) {
    const prefixA = [0];
    const prefixB = [0];
    const minDiff = [
      [Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER],
      [Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER],
    ];
    let left = 0;

    for (let index = 0; index < n; index++) {
      const num = Number(s[index]);
      const countA = prefixA.at(-1) + (num === a ? 1 : 0);
      const countB = prefixB.at(-1) + (num === b ? 1 : 0);

      prefixA.push(countA);
      prefixB.push(countB);

      while (index - left + 1 >= k && countA > prefixA[left] && countB > prefixB[left]) {
        const modA = prefixA[left] % 2;
        const modB = prefixB[left] % 2;

        minDiff[modA][modB] = Math.min(prefixA[left] - prefixB[left], minDiff[modA][modB]);
        left += 1;
      }
      const modA = prefixA.at(-1) % 2;
      const modB = prefixB.at(-1) % 2;
      const diff = prefixA.at(-1) - prefixB.at(-1) - minDiff[1 - modA][modB];

      result = Math.max(diff, result);
    }
  }

  return result;
};