commit d1fb87cbb1e1978a63165c5b3685c866e86e9373
parent 86230669f5cfa089b960e3eda32aa38c18954c80
Author: Jack Sangdahl <jack@pngu.org>
Date: Thu, 16 Oct 2025 21:03:05 -0600
3003. maximise the number of partitions after operations
Diffstat:
2 files changed, 175 insertions(+), 0 deletions(-)
diff --git a/max_num_partition_op.c b/max_num_partition_op.c
@@ -0,0 +1,87 @@
+// 3003. Maximize the Number of Partitions After Operations
+#include "leetcode.h"
+
+/*
+ * you are given a string 's' and an integer 'k'. first, you are allowed to
+ * change at mose one index in 's' to another lowercase english letter. after
+ * that, do the following partitioning operation until 's' is empty: chose the
+ * longest prefix of 's' containing at most 'k' distinct characters, and 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 chosing at most one index to change.
+ */
+
+#define ALPHA_SIZE 26
+
+int maxPartitionsAfterOperations(char *s, int k) {
+ if (k == ALPHA_SIZE)
+ return 1;
+ int n = strlen(s), used = 0, cnt = 0, ans = 1;
+ int *ansr = (int *)calloc(n, sizeof(int));
+ int *usedr = (int *)calloc(n, sizeof(int));
+ for (int i = n - 1; i >= 0; i--) {
+ int curr = s[i] - 'a';
+ if (!(used & (1 << curr))) {
+ if (cnt == k) {
+ cnt = 0;
+ used = 0;
+ ans++;
+ }
+ used |= 1 << curr;
+ cnt++;
+ }
+ ansr[i] = ans;
+ usedr[i] = used;
+ }
+ int ansl = 0, l = 0;
+ ans = ansr[0];
+ while (l < n) {
+ used = cnt = 0;
+ int used_prev = 0, used_2_prev = 0, last = -1, r = l;
+ while (r < n) {
+ int curr = s[r] - 'a';
+ if (!(used & (1 << curr))) {
+ if (cnt == k)
+ break;
+ used_prev = used;
+ last = r;
+ used |= 1 << curr;
+ cnt++;
+ } else if (cnt < k)
+ used_2_prev |= 1 << curr;
+ r++;
+ }
+ if (cnt == k) {
+ if (last - 1 > __builtin_popcount(used_prev))
+ ans = fmax(ans, ansl + 1 + ansr[last]);
+ if (last + 1 < r) {
+ if (last + 2 >= n)
+ ans = fmax(ans, ansl + 1 + 1);
+ else {
+ if (__builtin_popcount(usedr[last + 2]) == k) {
+ int valid = ((1 << ALPHA_SIZE) - 1) & ~used & ~usedr[last + 2];
+ ans = fmax(ans, valid > 0 ? ansl + 1 + 1 + ansr[last + 2]
+ : ansl + 1 + ansr[last + 2]);
+ int l1 = s[last + 1] - 'a';
+ if (!(used_2_prev & (1 << l1)))
+ ans = fmax(ans, ansl + 1 + ansr[last + 1]);
+ } else
+ ans = fmax(ans, ansl + 1 + ansr[last + 2]);
+ }
+ }
+ }
+ l = r;
+ ansl++;
+ }
+ free(ansr);
+ free(usedr);
+ return ans;
+}
+
+int main() {
+ char *s1 = "accca", *s2 = "aabaab", *s3 = "xxyz";
+ printf("%d\n", maxPartitionsAfterOperations(s1, 2)); // expect: 3
+ printf("%d\n", maxPartitionsAfterOperations(s2, 3)); // expect: 1
+ printf("%d\n", maxPartitionsAfterOperations(s3, 1)); // expect: 4
+}
diff --git a/max_num_partition_op.py b/max_num_partition_op.py
@@ -0,0 +1,88 @@
+# 3003. Maximize the Number of Partitions After Operations
+
+"""
+you are given a string 's' and an integer 'k'. first, you are allowed to
+change at mose one index in 's' to another lowercase english letter. after
+that, do the following partitioning operation until 's' is empty: chose the
+longest prefix of 's' containing at most 'k' distinct characters, and 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 chosing at most one index to change.
+"""
+
+
+class Solution(object):
+ def maxPartitionsAfterOperations(self, s, k):
+ """
+ :type s: str
+ :type k: int
+ :rtype: int
+ """
+ alpha_size = 26
+ if k == alpha_size:
+ return 1
+ n, used, cnt, ans = len(s), 0, 0, 1
+ ansr = [0] * n
+ usedr = [0] * n
+ for i in range(n - 1, -1, -1):
+ curr = ord(s[i]) - ord("a")
+ if (used & (1 << curr)) == 0:
+ if cnt == k:
+ cnt = 0
+ used = 0
+ ans += 1
+ used |= 1 << curr
+ cnt += 1
+ ansr[i] = ans
+ usedr[i] = used
+ ansl = 0
+ ans = ansr[0]
+ l = 0
+ while l < n:
+ used = 0
+ cnt = 0
+ used_prev = 0
+ used_2_prev = 0
+ last = -1
+ r = l
+ while r < n:
+ curr = ord(s[r]) - ord("a")
+ if (used & (1 << curr)) == 0:
+ if cnt == k:
+ break
+ used_prev = used
+ last = r
+ used |= 1 << curr
+ cnt += 1
+ elif cnt < k:
+ used_2_prev |= 1 << curr
+ r += 1
+ if cnt == k:
+ if last - l > bin(used_prev).count("1"):
+ ans = max(ans, ansl + 1 + ansr[last])
+ if last + 1 < r:
+ if last + 2 >= n:
+ ans = max(ans, ansl + 1 + 1)
+ else:
+ if bin(usedr[last + 2]).count("1") == k:
+ valid = ((1 << alpha_size) - 1) & ~used & ~usedr[last + 2]
+ if valid > 0:
+ ans = max(ans, ansl + 1 + 1 + ansr[last + 2])
+ else:
+ ans = max(ans, ansl + 1 + ansr[last + 2])
+ l1 = ord(s[last + 1]) - ord("a")
+ if (used_2_prev & (1 << l1)) == 0:
+ ans = max(ans, ansl + 1 + ansr[last + 1])
+ else:
+ ans = max(ans, ansl + 1 + ansr[last + 2])
+ l = r
+ ansl += 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxPartitionsAfterOperations(s="accca", k=2))
+ print(obj.maxPartitionsAfterOperations(s="aabaab", k=3))
+ print(obj.maxPartitionsAfterOperations(s="xxyz", k=1))
