Maximize the Number of Partitions After Operations

Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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:

  1. The longest prefix containing at most 2 distinct characters is `"ac"`, we remove it and `s` becomes `"bca"`.
  2. Now The longest prefix containing at most 2 distinct characters is `"bc"`, so we remove it and `s` becomes `"a"`.
  3. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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^4
s consists only of lowercase English letters.
1 <= k <= 26

Solution

Method 1 – Greedy Partitioning with One Change Simulation

Intuition

To maximize the number of partitions, we want to maximize the number of times we can take a prefix with at most k distinct characters. By changing at most one character, we can try all possible single-character changes and simulate the partitioning process for each, taking the maximum result.

Approach

For each index in s, try changing it to every possible lowercase letter (other than the current one).
For each modified string, simulate the partitioning process:
- Start from the beginning, greedily take the longest prefix with at most k distinct characters, remove it, and repeat.
- Count the number of partitions.
Also consider the case where no change is made.
Return the maximum number of partitions found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int maxPartitionsAfterOperations(string s, int k) {
        int n = s.size(), ans = 0;
        auto getPartitions = [&](string t) {
            int cnt = 0, l = 0;
            while (l < n) {
                unordered_set<char> st;
                int r = l;
                while (r < n && (st.count(t[r]) || st.size() < k)) {
                    st.insert(t[r]);
                    r++;
                }
                cnt++;
                l = r;
            }
            return cnt;
        };
        ans = getPartitions(s);
        for (int i = 0; i < n; ++i) {
            for (char c = 'a'; c <= 'z'; ++c) {
                if (c == s[i]) continue;
                string t = s;
                t[i] = c;
                ans = max(ans, getPartitions(t));
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int maxPartitionsAfterOperations(String s, int k) {
        int n = s.length(), ans = 0;
        ans = getPartitions(s, k);
        for (int i = 0; i < n; i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == s.charAt(i)) continue;
                StringBuilder t = new StringBuilder(s);
                t.setCharAt(i, c);
                ans = Math.max(ans, getPartitions(t.toString(), k));
            }
        }
        return ans;
    }
    private int getPartitions(String s, int k) {
        int n = s.length(), cnt = 0, l = 0;
        while (l < n) {
            Set<Character> st = new HashSet<>();
            int r = l;
            while (r < n && (st.contains(s.charAt(r)) || st.size() < k)) {
                st.add(s.charAt(r));
                r++;
            }
            cnt++;
            l = r;
        }
        return cnt;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
        def get_partitions(t: str) -> int:
            n = len(t)
            cnt = 0
            l = 0
            while l < n:
                st = set()
                r = l
                while r < n and (t[r] in st or len(st) < k):
                    st.add(t[r])
                    r += 1
                cnt += 1
                l = r
            return cnt
        ans = get_partitions(s)
        n = len(s)
        for i in range(n):
            for c in map(chr, range(97, 123)):
                if c == s[i]:
                    continue
                t = s[:i] + c + s[i+1:]
                ans = max(ans, get_partitions(t))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
impl Solution {
    pub fn max_partitions_after_operations(s: String, k: i32) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let mut ans = get_partitions(s, k);
        for i in 0..n {
            for c in b'a'..=b'z' {
                if c == s[i] { continue; }
                let mut t = s.to_vec();
                t[i] = c;
                ans = ans.max(get_partitions(&t, k));
            }
        }
        ans
    }
}
fn get_partitions(s: &[u8], k: i32) -> i32 {
    let n = s.len();
    let mut cnt = 0;
    let mut l = 0;
    while l < n {
        let mut st = std::collections::HashSet::new();
        let mut r = l;
        while r < n && (st.contains(&s[r]) || st.len() < k as usize) {
            st.insert(s[r]);
            r += 1;
        }
        cnt += 1;
        l = r;
    }
    cnt
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function maxPartitionsAfterOperations(s: string, k: number): number {
    function getPartitions(t: string): number {
        let n = t.length, cnt = 0, l = 0;
        while (l < n) {
            const st = new Set<string>();
            let r = l;
            while (r < n && (st.has(t[r]) || st.size < k)) {
                st.add(t[r]);
                r++;
            }
            cnt++;
            l = r;
        }
        return cnt;
    }
    let ans = getPartitions(s);
    for (let i = 0; i < s.length; i++) {
        for (let c = 97; c <= 122; c++) {
            const ch = String.fromCharCode(c);
            if (ch === s[i]) continue;
            const t = s.slice(0, i) + ch + s.slice(i+1);
            ans = Math.max(ans, getPartitions(t));
        }
    }
    return ans;
};

Complexity

⏰ Time complexity: O(n * 26 * n) — for each index and each letter, we simulate the partitioning process.
🧺 Space complexity: O(n) — for temporary strings and sets.

Method 2 — DP with bitmask and memoization (efficient)

Intuition

The brute-force simulation in Method 1 re-simulates partitioning for many candidate single-character edits and therefore becomes too slow. We can speed this up using dynamic programming. Represent the set of distinct letters in the current active prefix as a 26-bit bitmask; bitwise OR and bit-count operations (mask | (1 << c), Integer.bitCount(mask)) update and measure distinct letters cheaply. The DP state is the triple (index, mask, canChange) and memoizing results avoids revisiting the same subproblems.

Approach

Define a recursive helper dp(index, mask, canChange) that returns the maximum number of additional partitions possible starting at index when the active prefix has letters denoted by mask and canChange indicates whether the single allowed character-change is still available.

If index == len(s) return 0 (no more characters → no more partitions).
Let c = s.charAt(index) and compute mask' = mask | (1 << (c - 'a')) and distinct = popcount(mask').
- If distinct <= k, we can continue the current prefix: candidate = dp(index+1, mask', canChange).
- If distinct > k, the active prefix must end before this character: candidate = 1 + dp(index+1, 1 << (c - 'a'), canChange) (we start a new prefix containing only the current character).
If canChange is true, try substituting the current character by each letter x in [0..25]:
- Compute maskX = mask | (1 << x) and distinctX = popcount(maskX).
- If distinctX <= k, consider dp(index+1, maskX, false).
- Otherwise consider 1 + dp(index+1, 1 << x, false).
- Keep the maximum over all choices.
Memoize the computed result for (index, mask, canChange) and return it. The initial call is dp(0, 0, true) + 1 (we add 1 to convert the “additional partitions” count to total partitions).

Complexity

⏰ Time complexity: O(n * M) – Each DP state (index, mask, flag) is computed once; in the worst case we may explore up to M different masks reachable from each index (practically much smaller than 2^26) and when canChange is true we try up to 26 substitutions.
🧺 Space complexity: O(n * M) – Memoization stores results per reachable (index, mask, flag) state.

Code

1
2

##### C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
using namespace std;

class Solution {
public:
    unordered_map<long long, int> memo;
    string s;
    int k;

    int maxPartitionsAfterOperations(string s_, int k_) {
        s = move(s_);
        k = k_;
        memo.clear();
        return dp(0, 0, true) + 1;
    }

private:
    int dp(int index, int mask, bool canChange) {
        if (index == (int)s.size()) return 0;
        long long key = (((long long)index) << 27) | (((long long)mask) << 1) | (canChange ? 1LL : 0LL);
        auto it = memo.find(key);
        if (it != memo.end()) return it->second;

        int ch = s[index] - 'a';
        int maskUpdated = mask | (1 << ch);
        int distinct = __builtin_popcount(maskUpdated);

        int res;
        if (distinct > k) {
            res = 1 + dp(index + 1, 1 << ch, canChange);
        } else {
            res = dp(index + 1, maskUpdated, canChange);
        }

        if (canChange) {
            for (int nc = 0; nc < 26; ++nc) {
                int maskNew = mask | (1 << nc);
                int d2 = __builtin_popcount(maskNew);
                if (d2 > k) {
                    res = max(res, 1 + dp(index + 1, 1 << nc, false));
                } else {
                    res = max(res, dp(index + 1, maskNew, false));
                }
            }
        }

        memo[key] = res;
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package main

type Solution struct {
    memo map[int]int64 // use int64 keys stored as map values
    s    string
    k    int
}

func (sol *Solution) maxPartitionsAfterOperations(s string, k int) int {
    sol.s = s
    sol.k = k
    sol.memo = make(map[int]int64)
    return sol.dp(0, 0, true) + 1
}

func (sol *Solution) dp(index int, mask int, canChange bool) int {
    if index == len(sol.s) {
        return 0
    }
    key := (index << 27) | (mask << 1)
    if canChange {
        key |= 1
    }
    if val, ok := sol.memo[key]; ok {
        return int(val)
    }

    ch := int(sol.s[index]-'a')
    maskUpdated := mask | (1 << ch)
    distinct := bitsOn(maskUpdated)

    var res int
    if distinct > sol.k {
        res = 1 + sol.dp(index+1, 1<<ch, canChange)
    } else {
        res = sol.dp(index+1, maskUpdated, canChange)
    }

    if canChange {
        for nc := 0; nc < 26; nc++ {
            maskNew := mask | (1 << nc)
            d2 := bitsOn(maskNew)
            if d2 > sol.k {
                res = max(res, 1+sol.dp(index+1, 1<<nc, false))
            } else {
                res = max(res, sol.dp(index+1, maskNew, false))
            }
        }
    }

    sol.memo[key] = int64(res)
    return res
}

// helper functions
func bitsOn(x int) int {
    cnt := 0
    for x != 0 {
        x &= x - 1
        cnt++
    }
    return cnt
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    private final HashMap<Long, Integer> memo = new HashMap<>();
    private String s;
    private int k;

    public int maxPartitionsAfterOperations(String s, int k) {
        this.s = s;
        this.k = k;
        memo.clear();
        return dp(0, 0, true) + 1;
    }

    private int dp(int index, int mask, boolean canChange) {
        if (index == s.length()) return 0;

        long key = (((long) index) << 27) | (((long) mask) << 1) | (canChange ? 1L : 0L);
        if (memo.containsKey(key)) return memo.get(key);

        int ch = s.charAt(index) - 'a';
        int maskUpdated = mask | (1 << ch);
        int distinct = Integer.bitCount(maskUpdated);

        int res;
        if (distinct > k) {
            res = 1 + dp(index + 1, 1 << ch, canChange);
        } else {
            res = dp(index + 1, maskUpdated, canChange);
        }

        if (canChange) {
            for (int nc = 0; nc < 26; nc++) {
                int maskNew = mask | (1 << nc);
                int d2 = Integer.bitCount(maskNew);
                if (d2 > k) {
                    res = Math.max(res, 1 + dp(index + 1, 1 << nc, false));
                } else {
                    res = Math.max(res, dp(index + 1, maskNew, false));
                }
            }
        }

        memo.put(key, res);
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    private val memo = HashMap<Long, Int>()
    private lateinit var s: String
    private var k: Int = 0

    fun maxPartitionsAfterOperations(s: String, k: Int): Int {
        this.s = s
        this.k = k
        memo.clear()
        return dp(0, 0, true) + 1
    }

    private fun dp(index: Int, mask: Int, canChange: Boolean): Int {
        if (index == s.length) return 0
        val key = (index.toLong() shl 27) or (mask.toLong() shl 1) or if (canChange) 1L else 0L
        memo[key]?.let { return it }

        val ch = s[index] - 'a'
        val maskUpdated = mask or (1 shl ch)
        val distinct = Integer.bitCount(maskUpdated)

        var res = if (distinct > k) {
            1 + dp(index + 1, 1 shl ch, canChange)
        } else {
            dp(index + 1, maskUpdated, canChange)
        }

        if (canChange) {
            for (nc in 0 until 26) {
                val maskNew = mask or (1 shl nc)
                val d2 = Integer.bitCount(maskNew)
                res = if (d2 > k) {
                    maxOf(res, 1 + dp(index + 1, 1 shl nc, false))
                } else {
                    maxOf(res, dp(index + 1, maskNew, false))
                }
            }
        }

        memo[key] = res
        return res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
        self.s = s
        self.k = k
        self.memo: dict[int, int] = {}
        return self.dp(0, 0, True) + 1

    def dp(self, index: int, mask: int, canChange: bool) -> int:
        if index == len(self.s):
            return 0

        key = (index << 27) | (mask << 1) | (1 if canChange else 0)
        if key in self.memo:
            return self.memo[key]

        ch = ord(self.s[index]) - ord('a')
        mask_updated = mask | (1 << ch)
        distinct = mask_updated.bit_count()

        if distinct > self.k:
            res = 1 + self.dp(index + 1, 1 << ch, canChange)
        else:
            res = self.dp(index + 1, mask_updated, canChange)

        if canChange:
            for nc in range(26):
                mask_new = mask | (1 << nc)
                d2 = mask_new.bit_count()
                if d2 > self.k:
                    res = max(res, 1 + self.dp(index + 1, 1 << nc, False))
                else:
                    res = max(res, self.dp(index + 1, mask_new, False))

        self.memo[key] = res
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
impl Solution {
    pub fn maxPartitionsAfterOperations(s: String, k: i32) -> i32 {
        let bytes = s.into_bytes();
        let n = bytes.len();
        let mut memo = std::collections::HashMap::<i64, i32>::new();

        fn dp(bytes: &[u8], n: usize, index: usize, mask: i32, can_change: bool, k: i32, memo: &mut std::collections::HashMap<i64, i32>) -> i32 {
            if index == n { return 0; }
            let key = ((index as i64) << 27) | ((mask as i64) << 1) | if can_change { 1 } else { 0 };
            if let Some(&v) = memo.get(&key) { return v; }

            let ch = (bytes[index] - b'a') as i32;
            let mask_updated = mask | (1 << ch);
            let distinct = (mask_updated as u32).count_ones() as i32;

            let mut res = if distinct > k {
                1 + dp(bytes, n, index + 1, 1 << ch, can_change, k, memo)
            } else {
                dp(bytes, n, index + 1, mask_updated, can_change, k, memo)
            };

            if can_change {
                for nc in 0..26 {
                    let mask_new = mask | (1 << nc);
                    let d2 = (mask_new as u32).count_ones() as i32;
                    if d2 > k {
                        res = res.max(1 + dp(bytes, n, index + 1, 1 << nc, false, k, memo));
                    } else {
                        res = res.max(dp(bytes, n, index + 1, mask_new, false, k, memo));
                    }
                }
            }

            memo.insert(key, res);
            res
        }

        dp(&bytes, n, 0, 0, true, k, &mut memo)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
function maxPartitionsAfterOperations(s: string, k: number): number {
    const memo = new Map<number, number>();
    const n = s.length;

    function dp(index: number, mask: number, canChange: boolean): number {
        if (index === n) return 0;
        const key = (index << 27) | (mask << 1) | (canChange ? 1 : 0);
        if (memo.has(key)) return memo.get(key)!;

        const ch = s.charCodeAt(index) - 97;
        const maskUpdated = mask | (1 << ch);
        const distinct = bitCount(maskUpdated);

        let res: number;
        if (distinct > k) {
            res = 1 + dp(index + 1, 1 << ch, canChange);
        } else {
            res = dp(index + 1, maskUpdated, canChange);
        }

        if (canChange) {
            for (let nc = 0; nc < 26; nc++) {
                const maskNew = mask | (1 << nc);
                const d2 = bitCount(maskNew);
                if (d2 > k) {
                    res = Math.max(res, 1 + dp(index + 1, 1 << nc, false));
                } else {
                    res = Math.max(res, dp(index + 1, maskNew, false));
                }
            }
        }

        memo.set(key, res);
        return res;
    }

    function bitCount(x: number): number {
        let c = 0;
        while (x) {
            x &= x - 1;
            c++;
        }
        return c;
    }

    return dp(0, 0, true) + 1;
}

Method 3 — Bottom-up DP (iterative)

Intuition

We can convert the recursive DP into an iterative, sparse DP that processes the string from left to right. Instead of storing the result for every index, mask, and flag, we keep a sparse map of reachable (mask, flag) states after processing the first i characters and update it when we consume the next character. Each state stores the number of completed partitions so far; after processing all characters we add one for the final active prefix.

Approach

Use a sparse map cur mapping a packed key (mask, flag) -> completed_partitions after processing i characters. Pack a key as (mask << 1) | flag where flag is 1 if the single change is still available.
Initialize cur = { (0 << 1) | 1 : 0 } (no letters in active prefix, change still available, 0 completed partitions).
For each index i from 0 to n-1 with character c = s[i]:
- Create an empty next map.
- For every (mask, flag) in cur with value val:
  - Let maskUpdated = mask | (1 << (c - 'a')).
  - If popcount(maskUpdated) <= k, we can extend current prefix: update next[(maskUpdated, flag)] = max(next.get(...), val). Otherwise we must end the current prefix and start a new one containing c: update next[(1 << (c - 'a'), flag)] = max(..., val + 1).
  - If flag is 1, try substituting c with every nc in [0..25]:
    - Compute maskNew = mask | (1 << nc).
    - If popcount(maskNew) <= k update next[(maskNew, 0)] = max(..., val) else next[(1 << nc, 0)] = max(..., val + 1).
- Replace cur with next and continue.
After processing all n characters, the answer is max(cur.values()) + 1 (the final active prefix contributes one partition).

This forward (left-to-right) iterative DP is equivalent to the top-down memoized DP but easier to implement iteratively and to reason about reachable sparse states.

Complexity

⏰ Time complexity: O(n * S * 26) – For each of the n characters we iterate over the current sparse state set S and (when flag is true) may try up to 26 substitutions; in the worst case S equals the number of reachable masks times two flags.
🧺 Space complexity: O(S) – The sparse maps hold at most S reachable (mask, flag) states at any step.

Code

1
2

##### C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <string>
#include <unordered_map>
#include <climits>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxPartitionsAfterOperations(string s, int k) {
        int n = s.size();
        unordered_map<int,int> cur;
        cur[(0 << 1) | 1] = 0; // pack = (mask << 1) | flag

        for (int i = 0; i < n; ++i) {
            unordered_map<int,int> next;
            int ch = s[i] - 'a';

            for (auto &p : cur) {
                int packed = p.first;
                int val = p.second;
                int flag = packed & 1;
                int mask = packed >> 1;

                int maskUpdated = mask | (1 << ch);
                if (__builtin_popcount((unsigned)maskUpdated) <= k) {
                    int np = (maskUpdated << 1) | flag;
                    int curv = next.count(np) ? next[np] : INT_MIN;
                    next[np] = max(curv, val);
                } else {
                    int np = ((1 << ch) << 1) | flag;
                    int curv = next.count(np) ? next[np] : INT_MIN;
                    next[np] = max(curv, val + 1);
                }

                if (flag == 1) {
                    for (int nc = 0; nc < 26; ++nc) {
                        int maskNew = mask | (1 << nc);
                        if (__builtin_popcount((unsigned)maskNew) <= k) {
                            int np = (maskNew << 1) | 0;
                            int curv = next.count(np) ? next[np] : INT_MIN;
                            next[np] = max(curv, val);
                        } else {
                            int np = ((1 << nc) << 1) | 0;
                            int curv = next.count(np) ? next[np] : INT_MIN;
                            next[np] = max(curv, val + 1);
                        }
                    }
                }
            }

            cur.swap(next);
        }

        int ans = INT_MIN;
        for (auto &p : cur) ans = max(ans, p.second);
        return ans + 1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
package main

type Solution struct{}

func (sol *Solution) maxPartitionsAfterOperations(s string, k int) int {
    n := len(s)
    cur := make(map[int]int)
    cur[(0<<1)|1] = 0

    for i := 0; i < n; i++ {
        next := make(map[int]int)
        ch := int(s[i]-'a')

        for packed, val := range cur {
            flag := packed & 1
            mask := packed >> 1

            maskUpdated := mask | (1 << ch)
            if bitsOn(maskUpdated) <= k {
                np := (maskUpdated << 1) | flag
                if curv, ok := next[np]; ok {
                    if val > curv { next[np] = val }
                } else {
                    next[np] = val
                }
            } else {
                np := ((1 << ch) << 1) | flag
                if curv, ok := next[np]; ok {
                    if val+1 > curv { next[np] = val+1 }
                } else {
                    next[np] = val+1
                }
            }

            if flag == 1 {
                for nc := 0; nc < 26; nc++ {
                    maskNew := mask | (1 << nc)
                    if bitsOn(maskNew) <= k {
                        np := (maskNew << 1) | 0
                        if curv, ok := next[np]; ok {
                            if val > curv { next[np] = val }
                        } else {
                            next[np] = val
                        }
                    } else {
                        np := ((1 << nc) << 1) | 0
                        if curv, ok := next[np]; ok {
                            if val+1 > curv { next[np] = val+1 }
                        } else {
                            next[np] = val+1
                        }
                    }
                }
            }
        }

        cur = next
    }

    ans := -1<<31
    for _, v := range cur { if v > ans { ans = v } }
    return ans + 1
}

func bitsOn(x int) int {
    cnt := 0
    for x != 0 {
        x &= x - 1
        cnt++
    }
    return cnt
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public int maxPartitionsAfterOperations(String s, int k) {
        int n = s.length();
        // cur: packedKey -> completed partitions
        Map<Integer, Integer> cur = new HashMap<>();
        // packed: (mask << 1) | flag
        cur.put((0 << 1) | 1, 0);

        for (int i = 0; i < n; i++) {
            Map<Integer, Integer> next = new HashMap<>();
            int ch = s.charAt(i) - 'a';

            for (Map.Entry<Integer, Integer> e : cur.entrySet()) {
                int packed = e.getKey();
                int val = e.getValue();
                int flag = packed & 1;
                int mask = packed >>> 1;

                int maskUpdated = mask | (1 << ch);
                if (Integer.bitCount(maskUpdated) <= k) {
                    int np = (maskUpdated << 1) | flag;
                    next.put(np, Math.max(next.getOrDefault(np, Integer.MIN_VALUE), val));
                } else {
                    int np = ((1 << ch) << 1) | flag;
                    next.put(np, Math.max(next.getOrDefault(np, Integer.MIN_VALUE), val + 1));
                }

                if (flag == 1) {
                    for (int nc = 0; nc < 26; nc++) {
                        int maskNew = mask | (1 << nc);
                        if (Integer.bitCount(maskNew) <= k) {
                            int np = (maskNew << 1) | 0;
                            next.put(np, Math.max(next.getOrDefault(np, Integer.MIN_VALUE), val));
                        } else {
                            int np = ((1 << nc) << 1) | 0;
                            next.put(np, Math.max(next.getOrDefault(np, Integer.MIN_VALUE), val + 1));
                        }
                    }
                }
            }

            cur = next;
        }

        int ans = 0;
        for (int v : cur.values()) ans = Math.max(ans, v);
        return ans + 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    fun maxPartitionsAfterOperations(s: String, k: Int): Int {
        val n = s.length
        var cur = HashMap<Int, Int>()
        cur[(0 shl 1) or 1] = 0

        for (i in 0 until n) {
            val next = HashMap<Int, Int>()
            val ch = s[i] - 'a'

            for ((packed, val) in cur) {
                val flag = packed and 1
                val mask = packed ushr 1

                val maskUpdated = mask or (1 shl ch)
                if (Integer.bitCount(maskUpdated) <= k) {
                    val np = (maskUpdated shl 1) or flag
                    next[np] = maxOf(next.getOrDefault(np, Int.MIN_VALUE), val)
                } else {
                    val np = ((1 shl ch) shl 1) or flag
                    next[np] = maxOf(next.getOrDefault(np, Int.MIN_VALUE), val + 1)
                }

                if (flag == 1) {
                    for (nc in 0 until 26) {
                        val maskNew = mask or (1 shl nc)
                        if (Integer.bitCount(maskNew) <= k) {
                            val np = (maskNew shl 1) or 0
                            next[np] = maxOf(next.getOrDefault(np, Int.MIN_VALUE), val)
                        } else {
                            val np = ((1 shl nc) shl 1) or 0
                            next[np] = maxOf(next.getOrDefault(np, Int.MIN_VALUE), val + 1)
                        }
                    }
                }
            }

            cur = next
        }

        var ans = Int.MIN_VALUE
        for ((_, v) in cur) ans = maxOf(ans, v)
        return ans + 1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
        n = len(s)
        # cur: packed_key -> completed partitions ; pack = (mask << 1) | flag
        cur: dict[int, int] = {(0 << 1) | 1: 0}

        for i in range(n):
            nxt: dict[int, int] = {}
            ch = ord(s[i]) - ord('a')

            for packed, val in cur.items():
                flag = packed & 1
                mask = packed >> 1

                mask_updated = mask | (1 << ch)
                if mask_updated.bit_count() <= k:
                    np = (mask_updated << 1) | flag
                    nxt[np] = max(nxt.get(np, -10**9), val)
                else:
                    np = ((1 << ch) << 1) | flag
                    nxt[np] = max(nxt.get(np, -10**9), val + 1)

                if flag:
                    for nc in range(26):
                        mask_new = mask | (1 << nc)
                        if mask_new.bit_count() <= k:
                            np = (mask_new << 1) | 0
                            nxt[np] = max(nxt.get(np, -10**9), val)
                        else:
                            np = ((1 << nc) << 1) | 0
                            nxt[np] = max(nxt.get(np, -10**9), val + 1)

            cur = nxt

        ans = 0
        for v in cur.values():
            ans = max(ans, v)
        return ans + 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
use std::collections::HashMap;

impl Solution {
    pub fn max_partitions_after_operations(s: String, k: i32) -> i32 {
        let bytes = s.into_bytes();
        let n = bytes.len();
        let mut cur: HashMap<i64, i32> = HashMap::new();
        cur.insert(((0i64) << 1) | 1, 0);

        for i in 0..n {
            let mut next: HashMap<i64, i32> = HashMap::new();
            let ch = (bytes[i] - b'a') as i32;

            for (&packed, &val) in cur.iter() {
                let flag = (packed & 1) as i32;
                let mask = (packed >> 1) as i32;

                let mask_updated = mask | (1 << ch);
                if (mask_updated as u32).count_ones() as i32 <= k {
                    let np = ((mask_updated as i64) << 1) | (flag as i64);
                    let curv = *next.get(&np).unwrap_or(&i32::MIN);
                    next.insert(np, std::cmp::max(curv, val));
                } else {
                    let np = (((1 << ch) as i64) << 1) | (flag as i64);
                    let curv = *next.get(&np).unwrap_or(&i32::MIN);
                    next.insert(np, std::cmp::max(curv, val + 1));
                }

                if flag == 1 {
                    for nc in 0..26 {
                        let mask_new = mask | (1 << nc);
                        if (mask_new as u32).count_ones() as i32 <= k {
                            let np = ((mask_new as i64) << 1) | 0;
                            let curv = *next.get(&np).unwrap_or(&i32::MIN);
                            next.insert(np, std::cmp::max(curv, val));
                        } else {
                            let np = (((1 << nc) as i64) << 1) | 0;
                            let curv = *next.get(&np).unwrap_or(&i32::MIN);
                            next.insert(np, std::cmp::max(curv, val + 1));
                        }
                    }
                }
            }

            cur = next;
        }

        let mut ans = i32::MIN;
        for &v in cur.values() { ans = ans.max(v); }
        ans + 1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
function maxPartitionsAfterOperations(s: string, k: number): number {
    const n = s.length;
    const cur = new Map<number, number>();
    cur.set((0 << 1) | 1, 0);

    function bitCount(x: number): number {
        let c = 0;
        while (x) { x &= x - 1; c++; }
        return c;
    }

    for (let i = 0; i < n; i++) {
        const next = new Map<number, number>();
        const ch = s.charCodeAt(i) - 97;

        for (const [packed, val] of cur.entries()) {
            const flag = packed & 1;
            const mask = packed >>> 1;

            const maskUpdated = mask | (1 << ch);
            if (bitCount(maskUpdated) <= k) {
                const np = (maskUpdated << 1) | flag;
                next.set(np, Math.max(next.get(np) ?? Number.MIN_SAFE_INTEGER, val));
            } else {
                const np = ((1 << ch) << 1) | flag;
                next.set(np, Math.max(next.get(np) ?? Number.MIN_SAFE_INTEGER, val + 1));
            }

            if (flag === 1) {
                for (let nc = 0; nc < 26; nc++) {
                    const maskNew = mask | (1 << nc);
                    if (bitCount(maskNew) <= k) {
                        const np = (maskNew << 1) | 0;
                        next.set(np, Math.max(next.get(np) ?? Number.MIN_SAFE_INTEGER, val));
                    } else {
                        const np = ((1 << nc) << 1) | 0;
                        next.set(np, Math.max(next.get(np) ?? Number.MIN_SAFE_INTEGER, val + 1));
                    }
                }
            }
        }

        // replace cur with next
        cur.clear();
        for (const [k1, v1] of next.entries()) cur.set(k1, v1);
    }

    let ans = Number.MIN_SAFE_INTEGER;
    for (const v of cur.values()) ans = Math.max(ans, v);
    return ans + 1;
}

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Greedy Partitioning with One Change Simulation#

Intuition#

Approach#

Code#

Complexity#

Method 2 — DP with bitmask and memoization (efficient)#

Intuition#

Approach#

Complexity#

Code#

Method 3 — Bottom-up DP (iterative)#

Intuition#

Approach#

Complexity#

Code#

Problem

Examples

Example 1

Example 2

Example 3

Constraints

Solution

Method 1 – Greedy Partitioning with One Change Simulation

Intuition

Approach

Code

Complexity

Method 2 — DP with bitmask and memoization (efficient)

Intuition

Approach

Complexity

Code

Method 3 — Bottom-up DP (iterative)

Intuition

Approach

Complexity

Code