Missing Test Case - 3003. Maximize the Number of Partitions After Operations

[shaikh631]

LeetCode Username

ayan_9819

Problem Number, Title, and Link

https://leetcode.com/problems/maximize-the-number-of-partitions-after-operations/submissions/1804455405

Bug Category

Problem examples

Bug Description

Approach

Here’s how I solved it step by step:

I converted every character into a bitmask —
for example, 'a' → 1 << 0, 'b' → 1 << 1, etc.

Then, I defined a recursive DP function:

dp(i, canChange, mask)
i → current index in the string
canChange → whether I still can change one character (1 or 0)
mask → bitmask representing current distinct characters in this partition
For each character, I have two choices:

Add it to the current partition (if distinct count ≤ k)
Start a new partition (if adding it exceeds k)
If I still have the change option, I try changing the current character to all 26 possibilities and compute the best outcome.

Finally, the answer is dp(0, 1, 0) + 1
(we add 1 because the last segment counts as one partition).

Memoization ensures we don’t recompute the same states multiple times, making the solution efficient.

Language Used for Code

Java

Code used for Submit/Run operation

import java.util.*;

class Solution {
    private Map<Long, Integer> memo = new HashMap<>();
    private String s;
    private int k;

    private int dp(int i, long mask, boolean canChange) {
        if (i == s.length()) return 0;
        long key = ((long)i << 27) | (mask << 1) | (canChange ? 1 : 0);
        if (memo.containsKey(key)) return memo.get(key);

        int ch = s.charAt(i) - 'a';
        long newMask = mask | (1L << ch);
        int res;

        if (Long.bitCount(newMask) > k)
            res = 1 + dp(i + 1, 1L << ch, canChange);
        else
            res = dp(i + 1, newMask, canChange);

        if (canChange) {
            for (int j = 0; j < 26; j++) {
                long changeMask = mask | (1L << j);
                if (Long.bitCount(changeMask) > k)
                    res = Math.max(res, 1 + dp(i + 1, 1L << j, false));
                else
                    res = Math.max(res, dp(i + 1, changeMask, false));
            }
        }

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

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

Expected behavior

484. ms
     Beats. 33.33%

Screenshots

Additional context

No response

[exalate-issue-sync]

oj-leetcode commented: Hello ayan_9819,

Thank you for sharing your approach and detailed code for the problem "Maximize the Number of Partitions After Operations". However, to assist you further, we need more information on the specific nature of the issue related to problem examples. Are there inconsistencies or ambiguities in the examples that impact the understanding or functionality of your code? Any details on what you expected from the examples versus what was presented would be highly beneficial.

In the meantime, I recommend examining the problem statement and examples closely to ensure there are no overlooked details. It may also be helpful to discuss this with fellow users or on LeetCode's discussion forums, where community insights may provide additional clarity.

Looking forward to your response so we can assist you better.

LeetCode Support Team