Skip to content

3445. Maximum Difference Between Even and Odd Frequency II 👍

  • Time: $O(20n) = O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  int maxDifference(string s, int k) {
    int ans = INT_MIN;

    for (const auto& [a, b] : getPermutations()) {
      // minDiff[parityA][parityB] := min(a - b) of all valid windows with
      // parityA and parityB
      vector<vector<int>> minDiff(2, vector<int>(2, INT_MAX / 2));
      vector<int> prefixA{0};  // prefixA[i] := the number of 'a's in s[0..i)
      vector<int> prefixB{0};  // prefixB[i] := the number of 'b's in s[0..i)
      for (int l = 0, r = 0; r < s.length(); ++r) {
        prefixA.push_back(prefixA.back() + (s[r] == a ? 1 : 0));
        prefixB.push_back(prefixB.back() + (s[r] == b ? 1 : 0));
        while (r - l + 1 >= k &&               // the window size >= k
               prefixA[l] < prefixA.back() &&  // the number of 'a's > 0
               prefixB[l] < prefixB.back()) {  // the number of 'b's > 0
          minDiff[prefixA[l] % 2][prefixB[l] % 2] = min(
              minDiff[prefixA[l] % 2][prefixB[l] % 2], prefixA[l] - prefixB[l]);
          ++l;
        }
        ans = max(ans, (prefixA.back() - prefixB.back()) -
                           minDiff[1 - prefixA.back() % 2][prefixB.back() % 2]);
      }
    }

    return ans;
  }

 private:
  vector<pair<char, char>> getPermutations() {
    vector<pair<char, char>> permutations;
    for (const char a : "01234")
      for (const char b : "01234")
        if (a != b)
          permutations.emplace_back(a, b);
    return permutations;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
  public int maxDifference(String s, int k) {
    int ans = Integer.MIN_VALUE;

    for (Pair<Character, Character> pair : getPermutations()) {
      final char a = pair.getKey();
      final char b = pair.getValue();

      // minDiff[parityA][parityB] := min(a - b) of all valid windows with
      // parityA and parityB
      int[][] minDiff = new int[2][2];
      Arrays.stream(minDiff).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE / 2));
      // prefixA[i] := the number of 'a's in s[0..i)
      List<Integer> prefixA = new ArrayList<>(List.of(0));
      // prefixB[i] := the number of 'b's in s[0..i)
      List<Integer> prefixB = new ArrayList<>(List.of(0));
      for (int l = 0, r = 0; r < s.length(); ++r) {
        prefixA.add(prefixA.get(prefixA.size() - 1) + (s.charAt(r) == a ? 1 : 0));
        prefixB.add(prefixB.get(prefixB.size() - 1) + (s.charAt(r) == b ? 1 : 0));
        while (r - l + 1 >= k &&                                   // the window size >= k
               prefixA.get(l) < prefixA.get(prefixA.size() - 1) && // the number of 'a's > 0
               prefixB.get(l) < prefixB.get(prefixB.size() - 1)) { // the number of 'b's > 0
          minDiff[prefixA.get(l) % 2][prefixB.get(l) % 2] = Math.min(
              minDiff[prefixA.get(l) % 2][prefixB.get(l) % 2], prefixA.get(l) - prefixB.get(l));
          ++l;
        }
        ans = Math.max(ans, (prefixA.get(prefixA.size() - 1) - prefixB.get(prefixB.size() - 1)) -
                                minDiff[1 - prefixA.get(prefixA.size() - 1) % 2]
                                       [prefixB.get(prefixB.size() - 1) % 2]);
      }
    }

    return ans;
  }

  private List<Pair<Character, Character>> getPermutations() {
    List<Pair<Character, Character>> permutations = new ArrayList<>();
    for (final char a : "01234".toCharArray())
      for (final char b : "01234".toCharArray())
        if (a != b)
          permutations.add(new Pair<>(a, b));
    return permutations;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def maxDifference(self, s: str, k: int) -> int:
    ans = -math.inf
    permutations = [(a, b) for a in '01234' for b in '01234' if a != b]

    for a, b in permutations:
      # minDiff[(parityA, parityB)] := min(a - b) of all valid windows with
      # parityA and parityB
      minDiff = collections.defaultdict(lambda: math.inf)
      prefixA = [0]  # prefixA[i] := the number of 'a's in s[0..i)
      prefixB = [0]  # prefixB[i] := the number of 'b's in s[0..i)

      l = 0
      for r, c in enumerate(s):
        prefixA.append(prefixA[-1] + int(c == a))
        prefixB.append(prefixB[-1] + int(c == b))
        while (r - l + 1 >= k and  # the window size >= k
               prefixA[l] < prefixA[-1] and  # the number of 'a's > 0
               prefixB[l] < prefixB[-1]):  # the number of 'b's > 0
          paritiesKey = (prefixA[l] % 2, prefixB[l] % 2)
          minDiff[paritiesKey] = min(minDiff[paritiesKey],
                                     prefixA[l] - prefixB[l])
          l += 1
        ans = max(ans, (prefixA[-1] - prefixB[-1]) -
                  minDiff[(1 - prefixA[-1] % 2, prefixB[-1] % 2)])

    return ans