3445. 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 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.

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⁴
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 1

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;
    }
}

class Solution {
public:
    int maxDifference(string s, int k) {
        const int n = s.size();
        const int inf = INT_MAX / 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[2][2] = { {inf, inf}, {inf, inf} };
                int l = -1;

                for (int r = 0; r < n; ++r) {
                    curA += (s[r] == '0' + a);
                    curB += (s[r] == '0' + b);
                    while (r - l >= k && curB - preB >= 2) {
                        t[preA & 1][preB & 1] = min(t[preA & 1][preB & 1], preA - preB);
                        ++l;
                        preA += (s[l] == '0' + a);
                        preB += (s[l] == '0' + b);
                    }
                    ans = max(ans, curA - curB - t[(curA & 1) ^ 1][curB & 1]);
                }
            }
        }

        return ans;
    }
};

class Solution:
    def maxDifference(self, S: str, k: int) -> int:
        s = list(map(int, S))
        ans = -inf
        for a in range(5):
            for b in range(5):
                if a == b:
                    continue
                curA = curB = 0
                preA = preB = 0
                t = [[inf, inf], [inf, inf]]
                l = -1
                for r, x in enumerate(s):
                    curA += x == a
                    curB += x == b
                    while r - l >= k and curB - preB >= 2:
                        t[preA & 1][preB & 1] = min(t[preA & 1][preB & 1], preA - preB)
                        l += 1
                        preA += s[l] == a
                        preB += s[l] == b
                    ans = max(ans, curA - curB - t[curA & 1 ^ 1][curB & 1])
        return ans

func maxDifference(s string, k int) int {
	n := len(s)
	inf := math.MaxInt32 / 2
	ans := -inf

	for a := 0; a < 5; a++ {
		for b := 0; b < 5; b++ {
			if a == b {
				continue
			}
			curA, curB := 0, 0
			preA, preB := 0, 0
			t := [2][2]int{ {inf, inf}, {inf, inf} }
			l := -1

			for r := 0; r < n; r++ {
				if s[r] == byte('0'+a) {
					curA++
				}
				if s[r] == byte('0'+b) {
					curB++
				}

				for r-l >= k && curB-preB >= 2 {
					t[preA&1][preB&1] = min(t[preA&1][preB&1], preA-preB)
					l++
					if s[l] == byte('0'+a) {
						preA++
					}
					if s[l] == byte('0'+b) {
						preB++
					}
				}

				ans = max(ans, curA-curB-t[curA&1^1][curB&1])
			}
		}
	}

	return ans
}

function maxDifference(S: string, k: number): number {
    const s = S.split('').map(Number);
    let ans = -Infinity;
    for (let a = 0; a < 5; a++) {
        for (let b = 0; b < 5; b++) {
            if (a === b) {
                continue;
            }
            let [curA, curB, preA, preB] = [0, 0, 0, 0];
            const t: number[][] = [
                [Infinity, Infinity],
                [Infinity, Infinity],
            ];
            let l = -1;
            for (let r = 0; r < s.length; r++) {
                const x = s[r];
                curA += x === a ? 1 : 0;
                curB += x === 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] === a ? 1 : 0;
                    preB += s[l] === b ? 1 : 0;
                }
                ans = Math.max(ans, curA - curB - t[(curA & 1) ^ 1][curB & 1]);
            }
        }
    }
    return ans;
}

use std::cmp::{max, min};
use std::i32::{MAX, MIN};

impl Solution {
    pub fn max_difference(S: String, k: i32) -> i32 {
        let s: Vec<usize> = S
            .chars()
            .map(|c| c.to_digit(10).unwrap() as usize)
            .collect();
        let k = k as usize;
        let mut ans = MIN;

        for a in 0..5 {
            for b in 0..5 {
                if a == b {
                    continue;
                }

                let mut curA = 0;
                let mut curB = 0;
                let mut preA = 0;
                let mut preB = 0;
                let mut t = [[MAX; 2]; 2];
                let mut l: isize = -1;

                for (r, &x) in s.iter().enumerate() {
                    curA += (x == a) as i32;
                    curB += (x == b) as i32;

                    while (r as isize - l) as usize >= k && curB - preB >= 2 {
                        let i = (preA & 1) as usize;
                        let j = (preB & 1) as usize;
                        t[i][j] = min(t[i][j], preA - preB);
                        l += 1;
                        if l >= 0 {
                            preA += (s[l as usize] == a) as i32;
                            preB += (s[l as usize] == b) as i32;
                        }
                    }

                    let i = (curA & 1 ^ 1) as usize;
                    let j = (curB & 1) as usize;
                    if t[i][j] != MAX {
                        ans = max(ans, curA - curB - t[i][j]);
                    }
                }
            }
        }

        ans
    }
}

3445 - Maximum Difference Between Even and Odd Frequency II

3445. Maximum Difference Between Even and Odd Frequency II

Description

Solutions

Solution 1

All Problems

All Solutions

Welcome to Subscribe On Youtube

3445. Maximum Difference Between Even and Odd Frequency II

Description

Solutions

Solution 1

All Problems

All Solutions