Scale Engineer

Maximum Difference Between Even and Odd Frequency II

Hard
#3062Time: O(N³), where N is the length of the string. There are O(N²) substrings, and for each, we iterate up to N times to calculate frequencies. This is too slow for the given constraints.Space: O(1), as the frequency map size is constant (5 for digits '0'-'4').
Patterns
Sliding WindowEnumerationPrefix Sum
Data structures
String

Prompt

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 a non-zero 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

Approaches

3 approaches with complexity analysis and trade-offs.

The brute-force approach is the most straightforward way to solve the problem. It involves systematically checking every possible substring of the input string s, verifying if it meets the given criteria, and then calculating the potential difference to update a global maximum.

Algorithm

  • Use three nested loops to generate all substrings and calculate their character frequencies.
  • The outer loop i iterates from 0 to n-1 for the start of the substring.
  • The second loop j iterates from i to n-1 for the end of the substring.
  • Check if the substring length j - i + 1 is at least k.
  • If the length is valid, a third loop l from i to j calculates the frequency of each character ('0' through '4') in the substring s[i...j].
  • After calculating frequencies, iterate through all possible pairs of characters (a, b).
  • If freq[a] is odd and freq[b] is non-zero and even, calculate the difference freq[a] - freq[b].
  • Keep track of the maximum difference found across all valid substrings and character pairs.

Walkthrough

This method iterates through all possible start and end indices, i and j, to define a substring. For each substring, it first checks if its length is at least k. If it is, the algorithm then computes the frequency of each character within that specific substring. This is done by iterating through the substring's characters and using an array to store counts. Once the frequencies are known, it searches for a character a with an odd frequency and a character b with a non-zero, even frequency. For every such valid pair (a, b), it calculates freq[a] - freq[b] and updates the overall maximum difference found so far. This process is repeated for all substrings of length k or more.

class Solution {    public int maxDiff(String s, int k) {        int n = s.length();        int maxDifference = Integer.MIN_VALUE;        boolean found = false;         for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                if (j - i + 1 < k) {                    continue;                }                 int[] freq = new int[5];                for (int l = i; l <= j; l++) {                    freq[s.charAt(l) - '0']++;                }                 int maxOddFreq = -1;                int minEvenFreq = Integer.MAX_VALUE;                boolean hasOdd = false;                boolean hasEven = false;                 for (int charIdx = 0; charIdx < 5; charIdx++) {                    if (freq[charIdx] > 0) {                        if (freq[charIdx] % 2 != 0) {                            maxOddFreq = Math.max(maxOddFreq, freq[charIdx]);                            hasOdd = true;                        } else { // non-zero and even                            minEvenFreq = Math.min(minEvenFreq, freq[charIdx]);                            hasEven = true;                        }                    }                }                 if (hasOdd && hasEven) {                    maxDifference = Math.max(maxDifference, maxOddFreq - minEvenFreq);                    found = true;                }            }        }        // The problem guarantees a solution exists, but for robustness:        return found ? maxDifference : 0;     }}

Complexity

Time

O(N³), where N is the length of the string. There are O(N²) substrings, and for each, we iterate up to N times to calculate frequencies. This is too slow for the given constraints.

Space

O(1), as the frequency map size is constant (5 for digits '0'-'4').

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Extremely inefficient due to its cubic time complexity.

  • Will result in a 'Time Limit Exceeded' (TLE) error on platforms with typical time limits for the given constraints.

Solutions

class Solution {public  int maxDifference(String S, int k) {    char[] s = S.toCharArray();    int n = s.length;    final int inf = Integer.MAX_VALUE / 2;    int ans = -inf;    for (int a = 0; a < 5; ++a) {      for (int b = 0; b < 5; ++b) {        if (a == b) {          continue;        }        int curA = 0, curB = 0;        int preA = 0, preB = 0;        int[][] t = {{inf, inf}, {inf, inf}};        for (int l = -1, r = 0; r < n; ++r) {          curA += s[r] == '0' + a ? 1 : 0;          curB += s[r] == '0' + b ? 1 : 0;          while (r - l >= k && curB - preB >= 2) {            t[preA & 1][preB & 1] =                Math.min(t[preA & 1][preB & 1], preA - preB);            ++l;            preA += s[l] == '0' + a ? 1 : 0;            preB += s[l] == '0' + b ? 1 : 0;          }          ans = Math.max(ans, curA - curB - t[curA & 1 ^ 1][curB & 1]);        }      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem