Today I have done leetcode's October LeetCoding Challenge with cpp.

October LeetCoding Challenge 17

Description

Maximize the Number of Partitions After Operations

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.

Example 1:

Input: s = "accca", k = 2

Output: 3

Explanation:

The optimal way is to change s[2] to something other than a and c, for example, b. then it becomes "acbca".

Then we perform the operations:

The longest prefix containing at most 2 distinct characters is "ac", we remove it and s becomes "bca".
Now The longest prefix containing at most 2 distinct characters is "bc", so we remove it and s becomes "a".
Finally, we remove "a" and s becomes empty, so the procedure ends.

Doing the operations, the string is divided into 3 partitions, so the answer is 3.

Example 2:

Input: s = "aabaab", k = 3

Output: 1

Explanation:

Initially s contains 2 distinct characters, so whichever character we change, it will contain at most 3 distinct characters, so the longest prefix with at most 3 distinct characters would always be all of it, therefore the answer is 1.

Example 3:

Input: s = "xxyz", k = 1

Output: 4

Explanation:

The optimal way is to change s[0] or s[1] to something other than characters in s, for example, to change s[0] to w.

Then s becomes "wxyz", which consists of 4 distinct characters, so as k is 1, it will divide into 4 partitions.

Constraints:

1 <= s.length <= 10⁴
s consists only of lowercase English letters.
1 <= k <= 26

Solution

struct Data{
  short count = 0;
  short splits = 0;
  int mask = 0;
};
class Solution {
public:
  int maxPartitionsAfterOperations(string s, int k) {
    if(k == 26) return 1;
    int len = s.length();
    vector<Data> prefix(len);
    vector<Data> suffix(len);
    int mask = 0;
    int count = 0;
    int splits = 0;
    for(int i = 0; i < len - 1; prefix[i + 1].mask = mask, prefix[i + 1].splits = splits, prefix[i + 1].count = count, ++i) {
      int bit = (1 << (s[i] - 'a'));
      if(mask & bit) continue;
      count += 1;
      if(count <= k) {
        mask |= bit;
      } else {
        splits += 1;
        mask = bit;
        count = 1;
      }
    }
    mask = 0;
    count = 0;
    splits = 0;
    for(int i = len - 1; i ; suffix[i - 1].mask = mask, suffix[i - 1].splits = splits, suffix[i - 1].count = count, --i) {
      int bit = (1 << (s[i] - 'a'));
      if(mask & bit) continue;
      count += 1;
      if(count <= k) {
        mask |= bit;
      } else {
        splits += 1;
        mask = bit;
        count = 1;
      }
    }
    int answer = 0;
    for(int i = 0; i < len; ++i) {
      int segments = prefix[i].splits +suffix[i].splits + 2;
      int mask = prefix[i].mask | suffix[i].mask;
      int count = __builtin_popcount(mask);
      if(prefix[i].count == k && suffix[i].count == k && count < 26) {
        segments += 1;
      } else if(count + 1 <= k) {
        segments -= 1;
      }
      answer = max(answer, segments);
    }
    return answer;
  }
};

// Accepted
// 277/277 cases passed (1 ms)
// Your runtime beats 93.44 % of cpp submissions
// Your memory usage beats 99.18 % of cpp submissions (11 MB)

2025-10-17 Daily Challenge

October LeetCoding Challenge 17

Description

Solution