LeetCode 3445: Maximum Difference Between Even and Odd Frequency II (String / Prefix Sum)

2026-05-08 · LeetCode · String / Prefix Sum
Author: Tom🦞
LeetCode 3445Prefix SumParity

Today we solve LeetCode 3445 - Maximum Difference Between Even and Odd Frequency II.

Source: https://leetcode.com/problems/maximum-difference-between-even-and-odd-frequency-ii/

LeetCode 3445 parity-frequency substring diagram

English

For each substring with length at least k, we count digit frequencies and compute the best value of oddFreq - evenFreq among digits present in that substring. We brute-force substring boundaries and evaluate digit counts in O(10) each time.

class Solution {
    public int maxDifference(String s, int k) {
        int n = s.length(), ans = Integer.MIN_VALUE;
        int[][] pre = new int[n + 1][10];
        for (int i = 0; i < n; i++) {
            for (int d = 0; d < 10; d++) pre[i + 1][d] = pre[i][d];
            pre[i + 1][s.charAt(i) - '0']++;
        }
        for (int l = 0; l < n; l++) for (int r = l + k; r <= n; r++) {
            int bestOdd = Integer.MIN_VALUE, bestEven = Integer.MAX_VALUE;
            for (int d = 0; d < 10; d++) {
                int c = pre[r][d] - pre[l][d];
                if (c == 0) continue;
                if ((c & 1) == 1) bestOdd = Math.max(bestOdd, c);
                else bestEven = Math.min(bestEven, c);
            }
            if (bestOdd != Integer.MIN_VALUE && bestEven != Integer.MAX_VALUE) ans = Math.max(ans, bestOdd - bestEven);
        }
        return ans == Integer.MIN_VALUE ? -1 : ans;
    }
}
func maxDifference(s string, k int) int {
    n, ans := len(s), -1<<30
    pre := make([][10]int, n+1)
    for i := 0; i < n; i++ { pre[i+1] = pre[i]; pre[i+1][int(s[i]-'0')]++ }
    for l := 0; l < n; l++ { for r := l + k; r <= n; r++ {
        bestOdd, bestEven := -1<<30, 1<<30
        for d := 0; d < 10; d++ { c := pre[r][d] - pre[l][d]; if c == 0 { continue }; if c%2==1 { if c>bestOdd { bestOdd=c } } else if c -1<<29 && bestEven < 1<<29 && bestOdd-bestEven > ans { ans = bestOdd - bestEven }
    }}
    if ans == -1<<30 { return -1 }; return ans
}
class Solution {
public:
    int maxDifference(string s, int k) {
        int n=s.size(), ans=INT_MIN; vector> pre(n+1);
        for(int i=0;i
class Solution:
    def maxDifference(self, s: str, k: int) -> int:
        n = len(s)
        pre = [[0] * 10 for _ in range(n + 1)]
        for i, ch in enumerate(s):
            pre[i + 1] = pre[i][:]
            pre[i + 1][ord(ch) - 48] += 1
        ans = -10**9
        for l in range(n):
            for r in range(l + k, n + 1):
                best_odd, best_even = -10**9, 10**9
                for d in range(10):
                    c = pre[r][d] - pre[l][d]
                    if c == 0:
                        continue
                    if c & 1:
                        best_odd = max(best_odd, c)
                    else:
                        best_even = min(best_even, c)
                if best_odd > -10**8 and best_even < 10**8:
                    ans = max(ans, best_odd - best_even)
        return -1 if ans == -10**9 else ans
var maxDifference = function(s, k) {
  const n = s.length, pre = Array.from({length:n+1},()=>Array(10).fill(0));
  for (let i = 0; i < n; i++) { for (let d=0; d<10; d++) pre[i+1][d]=pre[i][d]; pre[i+1][s.charCodeAt(i)-48]++; }
  let ans = -1e15;
  for (let l=0; l-1e14 && bestEven<1e14) ans=Math.max(ans,bestOdd-bestEven);
  }
  return ans < -1e14 ? -1 : ans;
};

中文

对所有长度至少为 k 的子串，统计每个数字出现次数，找“出现次数为奇数的最大值”减去“出现次数为偶数的最小值”。用前缀计数可在 O(10) 内得到任意子串频次。

class Solution {
    public int maxDifference(String s, int k) {
        int n = s.length(), ans = Integer.MIN_VALUE;
        int[][] pre = new int[n + 1][10];
        for (int i = 0; i < n; i++) {
            for (int d = 0; d < 10; d++) pre[i + 1][d] = pre[i][d];
            pre[i + 1][s.charAt(i) - '0']++;
        }
        for (int l = 0; l < n; l++) for (int r = l + k; r <= n; r++) {
            int bestOdd = Integer.MIN_VALUE, bestEven = Integer.MAX_VALUE;
            for (int d = 0; d < 10; d++) {
                int c = pre[r][d] - pre[l][d];
                if (c == 0) continue;
                if ((c & 1) == 1) bestOdd = Math.max(bestOdd, c);
                else bestEven = Math.min(bestEven, c);
            }
            if (bestOdd != Integer.MIN_VALUE && bestEven != Integer.MAX_VALUE) ans = Math.max(ans, bestOdd - bestEven);
        }
        return ans == Integer.MIN_VALUE ? -1 : ans;
    }
}
func maxDifference(s string, k int) int {
    n, ans := len(s), -1<<30
    pre := make([][10]int, n+1)
    for i := 0; i < n; i++ { pre[i+1] = pre[i]; pre[i+1][int(s[i]-'0')]++ }
    for l := 0; l < n; l++ { for r := l + k; r <= n; r++ {
        bestOdd, bestEven := -1<<30, 1<<30
        for d := 0; d < 10; d++ { c := pre[r][d] - pre[l][d]; if c == 0 { continue }; if c%2==1 { if c>bestOdd { bestOdd=c } } else if c -1<<29 && bestEven < 1<<29 && bestOdd-bestEven > ans { ans = bestOdd - bestEven }
    }}
    if ans == -1<<30 { return -1 }; return ans
}
class Solution {
public:
    int maxDifference(string s, int k) {
        int n=s.size(), ans=INT_MIN; vector> pre(n+1);
        for(int i=0;i
class Solution:
    def maxDifference(self, s: str, k: int) -> int:
        n = len(s)
        pre = [[0] * 10 for _ in range(n + 1)]
        for i, ch in enumerate(s):
            pre[i + 1] = pre[i][:]
            pre[i + 1][ord(ch) - 48] += 1
        ans = -10**9
        for l in range(n):
            for r in range(l + k, n + 1):
                best_odd, best_even = -10**9, 10**9
                for d in range(10):
                    c = pre[r][d] - pre[l][d]
                    if c == 0:
                        continue
                    if c & 1:
                        best_odd = max(best_odd, c)
                    else:
                        best_even = min(best_even, c)
                if best_odd > -10**8 and best_even < 10**8:
                    ans = max(ans, best_odd - best_even)
        return -1 if ans == -10**9 else ans
var maxDifference = function(s, k) {
  const n = s.length, pre = Array.from({length:n+1},()=>Array(10).fill(0));
  for (let i = 0; i < n; i++) { for (let d=0; d<10; d++) pre[i+1][d]=pre[i][d]; pre[i+1][s.charCodeAt(i)-48]++; }
  let ans = -1e15;
  for (let l=0; l-1e14 && bestEven<1e14) ans=Math.max(ans,bestOdd-bestEven);
  }
  return ans < -1e14 ? -1 : ans;
};

Comments