[LeetCode] 3445. Maximum Difference Between Even and Odd Frequency II

https://leetcode.com/problems/maximum-difference-between-even-and-odd-frequency-ii/description/?envType=daily-question&envId=2025-06-11

leetcode - Maximum Difference Between Even and Odd Frequency II

문제 유형: 비트마스크, 브루트 포스, 누적합, 슬라이딩 윈도우

문제 난이도: Hard

 

문제

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.

 

문자열 s와 정수 k가 주어진다.

s의 어떤 부분문자열 subs에서 가능한 홀수빈도 - 짝수빈도의 최대값을 구하시오.

 

풀이

모든 순서쌍 (a, b)에 대해 확인할 것이다. a는 항상 홀수를 트래킹할거고, b는 항상 짝수를 트래킹할것이다.

단, 같으면 안되므로 같은 경우는 스킵해주자.

 

getStatus()함수를 만든다. a와 b의 개수의 홀짝 여부를 확인하기 위함이다.

이진수상으로 00, 01, 10, 11이 반환되게 하여 4가지 상태를 정의시키도록 한다.

 

best배열을 만들어서 각 4개의 상태별로 최소 차이를 기록하기 위해 만든다.

최소 차이를 기록하는 이유는, 

cntA, cntB는 현재 구간합의 a, b의 개수이고,

prevA, prevB는 이전 구간합의 a, b의 개수이다.

 

right를 밀면서, cntA및 cntB를 누적한다.

  right - left >= k이면서, cntB - prevB >= 2인동안,

  left를 밀며 구간을 좁히며, prevA와 prevB를 업데이트하고, best배열에 최소 차이를 기록한다.

그 뒤, right의 상태를 구하고, best[rightStatus ^ 0b10]을 통해서 반대 상태를 조회하여, 이 최소 차이가 이전에 기록된 적 있다면, 

정답을 업데이트해준다. 정답은 ans = max(ans, cntA - cntB - best[rightStatus ^ 0b10])으로 업데이트하면 된다.

best의 최소차이를 유지하는 이유가 바로 이전 상태까지의 윈도우에서자를 부분을 자르는 목적으로 쓰일 것이다.

0b10을 xor하는 이유는, a의개수상태는 반전시키고, b의 개수상태는 유지시켜서, a가 홀수개를 추적, b가 짝수개를 추적하도록 하는 목적이 있다.

 

구해진 최대 ans값을 리턴한다.

 

코드

C++

class Solution {
public:
    int maxDifference(string s, int k) {
        auto getStatus = [](int cntA, int cntB) -> int {
            return ((cntA & 1) << 1) | (cntB & 1);
        } ;

        int n = s.size();
        int ans = INT_MIN;
        for(char a = '0'; a <= '4'; a++) {
            for(char b = '0'; b <= '4'; b++) {
                if(a == b) continue;

                int best[4] = {INT_MAX, INT_MAX, INT_MAX, INT_MAX};
                int cntA = 0, cntB = 0;
                int prevA = 0, prevB = 0;
                int left = -1;
                for(int right = 0; right < n; right++) {
                    cntA += (s[right] == a);
                    cntB += (s[right] == b);
                    while(right - left >= k && cntB - prevB >= 2) {
                        int leftStatus = getStatus(prevA, prevB);
                        best[leftStatus] = min(best[leftStatus], prevA - prevB);
                        left++;
                        prevA += (s[left] == a);
                        prevB += (s[left] == b);
                    }
                    int rightStatus = getStatus(cntA, cntB);
                    if(best[rightStatus ^ 0b10] != INT_MAX) {
                        ans = max(ans, cntA - cntB - best[rightStatus ^ 0b10]);
                    }
                }
            }
        }
        return ans;
    }
};