[LeetCode] 3003. Maximize the Number of Partitions After Operations

https://leetcode.com/problems/maximize-the-number-of-partitions-after-operations/description/?envType=daily-question&envId=2025-10-17

leetcode - Maximize the number of partitions after operations

문제 유형: 누적 합, 비트마스킹

문제 난이도: Hard

 

문제

You are given a string s and an integer k.

First, you are allowed to change at most one index in s to another lowercase English letter.

After that, do the following partitioning operation until s is empty:

• Choose the longest prefix of s containing at most k distinct characters.
• Delete the prefix from s and increase the number of partitions by one. The remaining characters (if any) in s maintain their initial order.

Return an integer denoting the maximum number of resulting partitions after the operations by optimally choosing at most one index to change.

 

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

우선, 당신은 최대 1개의 인덱스의 문자를 골라다른 영문소문자로 바꿀 수 있다.

그 뒤, 다음의 파티셔닝 연산을 s가 남아있는 동안 계속한다:

- 최대 k개의 종류의 문자를 고르는 가장 긴 접두사를 고른다.

- 해당 접두사를 제거한다. 남은 부분은 처음 순서를 유지한다.

 

최대로 얻을 수 잇는 파티션의 수를 구하시오.

 

풀이

left[i]에는 s[0...i-1]까지의 문자열의 분할 정보를, 

right[i]에는 s[i+1...n-1]까지의 문자열의 분할 정보를 담는다.

각각은 [num, mask, count]의 형태로 저장한다.

num은 지금까지 생긴 조각의 개수, mask는 현재 문자집합의 비트마스크 표현, count는 현재 조각에 포함된 서로 다른 문자의 수를 말한다.

 

우선, left부터 구해보자.

i = 0부터 n-1이전까지 시행한다:

• 각 문자를 비트 자릿수로 변환한다. 'a'라면 000...0001, 'c'라면 000....0100 이다.
• 그 뒤, 새 문자가 현재 조각에 없는 문자라면, count를 1 증가하고, count가 k이하라면 mask에 계속 bitwise-or로 누적한다.
• count가 k를 넘으면, 새로운 파티션을 시작해야 한다. num을 1 증가하고, mask에는 현재 비트로만 초기화하고, count=1로 초기화해놓는다.
• 이전까지의 정보를 제공하는 것이 목적이므로, left[i+1]에 저장한다.

 

right도 반대 방향으로 적용해서, 각각의 i에서 right[i-1]에 저장한다.

 

이제, 각 위치 i에서 한 글자를 바꾼다고 가정할 것이다.

문자를 바꾸었을 때, 왼쪽 이웃과 오른쪽 이웃이 영향받는다.

 

각 인덱스 i를 기준으로 아래와 같이 생각할 수 있다:

[prefix ... left split] (i-th character) [rigth split... suffix]

처음 base case의 값은, left[i] + right[i]의 num값에 2를 더한다. left와 right는 i이전 및 이후에 대한 조각 결과이고, left의 맨 오른쪽과 right의 맨 왼쪽 부분은, 사실 추가로 더 요소가 올 수도 있다. 그래서 각 영향을 받은 활성 파티션을 고려해서 2를 더한 것이다.

 

1. (왼쪽 조각) + i + (오른쪽 조각)을 합쳐도 k 이하인 경우, 셋은 하나로 합쳐지므로, 조각의 수를 1개 제외한다.

2. 왼쪽 조각과 오른쪽 조각이 이미 각각 k개의 카운트를 가지고, 서로 다른 문자를 가진다면, i를 치환하여 세 개의 파티션으로 나눌 수 있다. 즉, 조각의 수를 1 더한다.

3. 그 외는, 2개 그대로 둔다.

 

이렇게 모든 인덱스에 대해 고려하여, 가장 큰 값을 리턴하면 된다.

 

코드

C++

class Solution {
public:
    int maxPartitionsAfterOperations(string s, int k) {
        int n = s.size();
        vector<vector<int>> left(n, vector<int>(3)), right(n, vector<int>(3));
        int num = 0, mask = 0, count = 0;
        for(int i = 0; i < n-1; i++) {
            int binary = 1 << (s[i] - 'a');
            if(!(mask & binary)) {
                count++;
                if(count <= k) {
                    mask |= binary;
                } else {
                    num++;
                    mask = binary;
                    count = 1;
                }
            }
            left[i+1][0] = num;
            left[i+1][1] = mask;
            left[i+1][2] = count;
        }

        num = 0, mask = 0; count = 0;
        for(int i = n-1; i > 0; i--) {
            int binary = 1 << (s[i] - 'a');
            if(!(mask & binary)) {
                count++;
                if(count <= k) {
                    mask |= binary;
                } else {
                    num++;
                    mask = binary;
                    count = 1;
                }
            } 
            right[i-1][0] = num;
            right[i-1][1] = mask;
            right[i-1][2] = count;
        }

        int ans = 0;
        for(int i = 0; i < n; i++) {
            int seg = left[i][0] + right[i][0] + 2; 
            int totMask = left[i][1] | right[i][1];
            int totCount = 0;
            while(totMask) {
                totMask = totMask & (totMask - 1);
                totCount++;
            }
            if(left[i][2] == k && right[i][2] == k && totCount < 26) {
                seg++;
            } else if(min(totCount+1, 26) <= k) {
                seg--;
            }
            ans = max(ans, seg);
        }
    
        return ans;
    }
};