Maximum Difference Between Even and Odd Frequency II

Problem

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.

Examples

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 * 10^4
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

Method 1 – Prefix Sum + Enumeration

Intuition

We want to find a substring of length at least k where the frequency of one character is odd and another is even, and maximize their difference. Since the string only contains digits '0' to '4', we can efficiently enumerate all possible substrings and use prefix sums to quickly compute character frequencies.

Approach

Precompute prefix sums for each character ('0' to '4') to allow O(1) frequency queries for any substring.
For every possible substring of length at least k, compute the frequency of each character.
For each substring, check all pairs (a, b) where a has odd frequency and b has even frequency.
Calculate freq[a] - freq[b] and update the answer if it's larger.
Return the maximum difference found.

Code

C++

class Solution {
public:
  int maxDifference(string s, int k) {
    int n = s.size(), ans = INT_MIN;
    vector<vector<int>> pre(5, vector<int>(n + 1, 0));
    for (int i = 0; i < n; ++i)
      for (int d = 0; d < 5; ++d)
        pre[d][i + 1] = pre[d][i] + (s[i] - '0' == d);
    for (int l = 0; l <= n - k; ++l) {
      for (int r = l + k; r <= n; ++r) {
        vector<int> cnt(5);
        for (int d = 0; d < 5; ++d)
          cnt[d] = pre[d][r] - pre[d][l];
        for (int a = 0; a < 5; ++a) {
          if (cnt[a] % 2 == 1) {
            for (int b = 0; b < 5; ++b) {
              if (cnt[b] % 2 == 0 && cnt[b] > 0)
                ans = max(ans, cnt[a] - cnt[b]);
            }
          }
        }
      }
    }
    return ans;
  }
};

Go

func maxDifference(s string, k int) int {
  n := len(s)
  pre := make([][]int, 5)
  for i := range pre {
    pre[i] = make([]int, n+1)
  }
  for i := 0; i < n; i++ {
    for d := 0; d < 5; d++ {
      pre[d][i+1] = pre[d][i]
    }
    pre[int(s[i]-'0')][i+1]++
  }
  ans := -1 << 31
  for l := 0; l <= n-k; l++ {
    for r := l + k; r <= n; r++ {
      cnt := make([]int, 5)
      for d := 0; d < 5; d++ {
        cnt[d] = pre[d][r] - pre[d][l]
      }
      for a := 0; a < 5; a++ {
        if cnt[a]%2 == 1 {
          for b := 0; b < 5; b++ {
            if cnt[b]%2 == 0 && cnt[b] > 0 {
              diff := cnt[a] - cnt[b]
              if diff > ans {
                ans = diff
              }
            }
          }
        }
      }
    }
  }
  return ans
}

Java

class Solution {
  public int maxDifference(String s, int k) {
    int n = s.length(), ans = Integer.MIN_VALUE;
    int[][] pre = new int[5][n + 1];
    for (int i = 0; i < n; ++i)
      for (int d = 0; d < 5; ++d)
        pre[d][i + 1] = pre[d][i] + ((s.charAt(i) - '0') == d ? 1 : 0);
    for (int l = 0; l <= n - k; ++l) {
      for (int r = l + k; r <= n; ++r) {
        int[] cnt = new int[5];
        for (int d = 0; d < 5; ++d)
          cnt[d] = pre[d][r] - pre[d][l];
        for (int a = 0; a < 5; ++a) {
          if (cnt[a] % 2 == 1) {
            for (int b = 0; b < 5; ++b) {
              if (cnt[b] % 2 == 0 && cnt[b] > 0)
                ans = Math.max(ans, cnt[a] - cnt[b]);
            }
          }
        }
      }
    }
    return ans;
  }
}

Kotlin

class Solution {
  fun maxDifference(s: String, k: Int): Int {
    val n = s.length
    val pre = Array(5) { IntArray(n + 1) }
    for (i in 0 until n)
      for (d in 0..4)
        pre[d][i + 1] = pre[d][i] + if (s[i] - '0' == d) 1 else 0
    var ans = Int.MIN_VALUE
    for (l in 0..n - k) {
      for (r in l + k..n) {
        val cnt = IntArray(5)
        for (d in 0..4)
          cnt[d] = pre[d][r] - pre[d][l]
        for (a in 0..4) {
          if (cnt[a] % 2 == 1) {
            for (b in 0..4) {
              if (cnt[b] % 2 == 0 && cnt[b] > 0)
                ans = maxOf(ans, cnt[a] - cnt[b])
            }
          }
        }
      }
    }
    return ans
  }
}

Python

class Solution:
  def maxDifference(self, s: str, k: int) -> int:
    n: int = len(s)
    pre: list[list[int]] = [[0] * (n + 1) for _ in range(5)]
    for i in range(n):
      for d in range(5):
        pre[d][i + 1] = pre[d][i] + (int(s[i]) == d)
    ans: int = float('-inf')
    for l in range(n - k + 1):
      for r in range(l + k, n + 1):
        cnt: list[int] = [pre[d][r] - pre[d][l] for d in range(5)]
        for a in range(5):
          if cnt[a] % 2 == 1:
            for b in range(5):
              if cnt[b] % 2 == 0 and cnt[b] > 0:
                ans = max(ans, cnt[a] - cnt[b])
    return ans

Rust

impl Solution {
  pub fn maximum_difference(s: String, k: i32) -> i32 {
    let n = s.len();
    let s = s.as_bytes();
    let mut pre = vec![vec![0; n + 1]; 5];
    for i in 0..n {
      for d in 0..5 {
        pre[d][i + 1] = pre[d][i] + if (s[i] - b'0') as usize == d { 1 } else { 0 };
      }
    }
    let mut ans = i32::MIN;
    for l in 0..=n - k as usize {
      for r in l + k as usize..=n {
        let mut cnt = vec![0; 5];
        for d in 0..5 {
          cnt[d] = pre[d][r] - pre[d][l];
        }
        for a in 0..5 {
          if cnt[a] % 2 == 1 {
            for b in 0..5 {
              if cnt[b] % 2 == 0 && cnt[b] > 0 {
                ans = ans.max(cnt[a] - cnt[b]);
              }
            }
          }
        }
      }
    }
    ans
  }
}

Complexity

⏰ Time complexity: O(n^3) (due to three nested loops: substring start, end, and character pairs; can be optimized further)
🧺 Space complexity: O(n) (for prefix sums)

Method 2 – Two pointers

Intuition

Since s contains only digits from '0' to '4', we can enumerate all possible pairs of distinct characters (a, b), where a must have an odd frequency and b an even frequency in the substring. We represent the parity of each character's count using bits: 0 for even, 1 for odd, resulting in four possible states for (a, b). The valid substring corresponds to the state where a is odd and b is even (binary 10).

We use a two-pointer technique: the right pointer expands the window, updating counts for a and b. The left pointer advances only when the substring length is at least k and b appears at least twice more in the window than before (to ensure an even, nonzero count). For each state, we maintain the minimum value of prev_a - prev_b in a best array indexed by the state of the left pointer.

For each right pointer position, we check if a valid left state exists (using XOR with 0b10), and update the answer with the difference (cnt_a - cnt_b) - best[status]. The maximum value found is returned as the answer.

Approach

For every pair of distinct digits a and b (from '0' to '4'):

Initialize an array best of size 4 (for all parity states), filled with infinity.
Set counters for a and b (cnt_a, cnt_b) and their prefix versions (prev_a, prev_b).
Use two pointers: left (starts at -1) and right (iterate over the string).

For each right:

Increment cnt_a and cnt_b if current character matches.
While window size is at least k and at least two new b's have been included, update best for the current left state and move left forward, updating prev_a and prev_b.
Compute the current parity state for cnt_a and cnt_b.
If a valid previous state exists (where a was odd and b even), update the answer with the difference.

Return the maximum answer found.

Code

C++

class Solution {
public:
  int maxDifference(std::string s, int k) {
   int n = s.size(), ans = INT_MIN;
   for (char a = '0'; a <= '4'; ++a) {
    for (char b = '0'; b <= '4'; ++b) {
      if (a == b) continue;
      int best[4];
      std::fill(best, best + 4, INT_MAX);
      int cnt_a = 0, cnt_b = 0, prev_a = 0, prev_b = 0, left = -1;
      for (int right = 0; right < n; ++right) {
       cnt_a += (s[right] == a);
       cnt_b += (s[right] == b);
       while (right - left >= k && cnt_b - prev_b >= 2) {
        int left_status = ((prev_a & 1) << 1) | (prev_b & 1);
        best[left_status] = std::min(best[left_status], prev_a - prev_b);
        ++left;
        prev_a += (s[left] == a);
        prev_b += (s[left] == b);
       }
       int right_status = ((cnt_a & 1) << 1) | (cnt_b & 1);
       if (best[right_status ^ 0b10] != INT_MAX) {
        ans = std::max(ans, cnt_a - cnt_b - best[right_status ^ 0b10]);
       }
      }
    }
   }
   return ans;
  }
};

Go

func maxDifference(s string, k int) int {
  n, ans := len(s), -1<<31
  for a := byte('0'); a <= '4'; a++ {
   for b := byte('0'); b <= '4'; b++ {
    if a == b {
      continue
    }
    best := [4]int{1<<31 - 1, 1<<31 - 1, 1<<31 - 1, 1<<31 - 1}
    cntA, cntB, prevA, prevB, left := 0, 0, 0, 0, -1
    for right := 0; right < n; right++ {
      if s[right] == a {
       cntA++
      }
      if s[right] == b {
       cntB++
      }
      for right-left >= k && cntB-prevB >= 2 {
       leftStatus := ((prevA & 1) << 1) | (prevB & 1)
       if best[leftStatus] > prevA-prevB {
        best[leftStatus] = prevA - prevB
       }
       left++
       if s[left] == a {
        prevA++
       }
       if s[left] == b {
        prevB++
       }
      }
      rightStatus := ((cntA & 1) << 1) | (cntB & 1)
      if best[rightStatus^0b10] != 1<<31-1 {
       diff := cntA - cntB - best[rightStatus^0b10]
       if diff > ans {
        ans = diff
       }
      }
    }
   }
  }
  return ans
}

Java

class Solution {
  public int maxDifference(String s, int k) {
   int n = s.length(), ans = Integer.MIN_VALUE;
   for (char a = '0'; a <= '4'; ++a) {
    for (char b = '0'; b <= '4'; ++b) {
      if (a == b) continue;
      int[] best = new int[4];
      Arrays.fill(best, Integer.MAX_VALUE);
      int cnt_a = 0, cnt_b = 0, prev_a = 0, prev_b = 0, left = -1;
      for (int right = 0; right < n; ++right) {
       cnt_a += (s.charAt(right) == a) ? 1 : 0;
       cnt_b += (s.charAt(right) == b) ? 1 : 0;
       while (right - left >= k && cnt_b - prev_b >= 2) {
        int left_status = ((prev_a & 1) << 1) | (prev_b & 1);
        best[left_status] = Math.min(best[left_status], prev_a - prev_b);
        ++left;
        prev_a += (s.charAt(left) == a) ? 1 : 0;
        prev_b += (s.charAt(left) == b) ? 1 : 0;
       }
       int right_status = ((cnt_a & 1) << 1) | (cnt_b & 1);
       if (best[right_status ^ 0b10] != Integer.MAX_VALUE) {
        ans = Math.max(ans, cnt_a - cnt_b - best[right_status ^ 0b10]);
       }
      }
    }
   }
   return ans;
  }
}

Kotlin

class Solution {
  fun maxDifference(s: String, k: Int): Int {
   val n = s.length
   var ans = Int.MIN_VALUE
   for (a in '0'..'4') {
    for (b in '0'..'4') {
      if (a == b) continue
      val best = IntArray(4) { Int.MAX_VALUE }
      var cntA = 0
      var cntB = 0
      var prevA = 0
      var prevB = 0
      var left = -1
      for (right in 0 until n) {
       if (s[right] == a) cntA++
       if (s[right] == b) cntB++
       while (right - left >= k && cntB - prevB >= 2) {
        val leftStatus = ((prevA and 1) shl 1) or (prevB and 1)
        best[leftStatus] = minOf(best[leftStatus], prevA - prevB)
        left++
        if (s[left] == a) prevA++
        if (s[left] == b) prevB++
       }
       val rightStatus = ((cntA and 1) shl 1) or (cntB and 1)
       if (best[rightStatus xor 0b10] != Int.MAX_VALUE) {
        ans = maxOf(ans, cntA - cntB - best[rightStatus xor 0b10])
       }
      }
    }
   }
   return ans
  }
}

Python

class Solution:
  def maxDifference(self, s: str, k: int) -> int:
   n: int = len(s)
   ans: int = float('-inf')
   for a in range(5):
    for b in range(5):
      if a == b:
       continue
      best: list[int] = [float('inf')] * 4
      cnt_a: int = 0
      cnt_b: int = 0
      prev_a: int = 0
      prev_b: int = 0
      left: int = -1
      for right in range(n):
       cnt_a += (int(s[right]) == a)
       cnt_b += (int(s[right]) == b)
       while right - left >= k and cnt_b - prev_b >= 2:
        left_status: int = ((prev_a & 1) << 1) | (prev_b & 1)
        best[left_status] = min(best[left_status], prev_a - prev_b)
        left += 1
        prev_a += (int(s[left]) == a)
        prev_b += (int(s[left]) == b)
       right_status: int = ((cnt_a & 1) << 1) | (cnt_b & 1)
       if best[right_status ^ 0b10] != float('inf'):
        ans = max(ans, cnt_a - cnt_b - best[right_status ^ 0b10])
   return ans

Rust

impl Solution {
  pub fn max_difference(s: String, k: i32) -> i32 {
   let n = s.len();
   let s = s.as_bytes();
   let mut ans = i32::MIN;
   for a in b'0'..=b'4' {
    for b in b'0'..=b'4' {
      if a == b { continue; }
      let mut best = [i32::MAX; 4];
      let (mut cnt_a, mut cnt_b, mut prev_a, mut prev_b, mut left) = (0, 0, 0, 0, -1);
      for right in 0..n {
       if s[right] == a { cnt_a += 1; }
       if s[right] == b { cnt_b += 1; }
       while (right as i32 - left) >= k && cnt_b - prev_b >= 2 {
        let left_status = ((prev_a & 1) << 1) | (prev_b & 1);
        best[left_status as usize] = best[left_status as usize].min(prev_a - prev_b);
        left += 1;
        if s[left as usize] == a { prev_a += 1; }
        if s[left as usize] == b { prev_b += 1; }
       }
       let right_status = ((cnt_a & 1) << 1) | (cnt_b & 1);
       let idx = (right_status ^ 0b10) as usize;
       if best[idx] != i32::MAX {
        ans = ans.max(cnt_a - cnt_b - best[idx]);
       }
      }
    }
   }
   ans
  }
}

Complexity

Time complexity: O(25 * n), since we check all pairs of digits (5*5=25) and scan the string for each.
Space complexity: O(1), only a few counters and a small array per pair.

Problem

Examples

Example 1

Example 2

Example 3

Constraints

Solution

Method 1 – Prefix Sum + Enumeration

Intuition

Approach

Code

C++

Go

Java

Kotlin

Python

Rust

Complexity

Method 2 – Two pointers

Intuition

Approach

Code

C++

Go

Java

Kotlin

Python

Rust

Complexity

Comments