Today I tackled LeetCode’s “Maximize the Number of Partitions After Operations” - a hard problem that took me through several hours iterations of debugging and optimization. Here’s the complete journey from broken code to accepted solution.

The Initial Disaster

I started with some skeleton code that didn’t even compile. The error was immediate and brutal:

Line 31: Char 5: error: non-void function does not return a value [-Werror,-Wreturn-type]
   31 |     }
      |     ^
1 error generated.

Classic mistake: I had a lambda function calculatePartitions that was supposed to return an integer, but the main function maxPartitionsAfterOperations never actually used it or returned anything. The function just… ended. Dead in the water before it even started lol.

First Attempt: The Naive Brute Force

My first instinct was to implement the most straightforward solution: try changing every character to every possible letter and count partitions each time. This seemed reasonable - just iterate through the string, mutate each position, count partitions, and track the maximum.

int maxPartitionsAfterOperations(string s, int k) {
    int basePartitions = countPartitions(s, k);
    int maxPartitions = basePartitions;
    
    for (int i = 0; i < n; ++i) {
        char original = s[i];
        for (char c = 'a'; c <= 'z'; ++c) {
            if (c != original) {
                s[i] = c;
                maxPartitions = max(maxPartitions, countPartitions(s, k));
                s[i] = original;
            }
        }
    }
    return maxPartitions;
}

I used bitmasks for tracking distinct characters in countPartitions, which was clever - a single integer to represent up to 26 letters using bit operations. Much faster than hash maps or arrays. The partition counting was O(n) and super clean.

But there was a problem.

The Time Limit Wall

Time Limit Exceeded
270 / 277 testcases passed

So close, yet so far. The algorithm was correct, but too slow. The complexity was O(n² × 26) - for each of n characters, I was trying 26 letters, and each try required scanning the entire string again to count partitions. On large inputs with n around 10⁴ or more, this exploded.

I needed something fundamentally faster.

The Breakthrough: Dynamic Programming with Memoization

The key insight was that this problem has overlapping subproblems. When processing position i with a certain set of distinct characters in the current partition, and having either used or not used the character change, the answer should be the same regardless of how we got there.

This screamed “memoization!”

I redesigned the solution as a top-down DP:

int dp(int i, int mask, bool changed) {
    if (i == s.size()) {
        return 0;
    }
    
    // Memoization key: pack position, bitmask, and changed flag
    long long key = ((long long)i << 27) | ((long long)mask << 1) | changed;
    if (memo.count(key)) {
        return memo[key];
    }
    
    // ... dp logic ...
}

The state space is:

i: current position in string (0 to n-1)
mask: bitmask of distinct characters in current partition (26 bits)
changed: whether we’ve used our one character change (1 bit)

At each position, I explore two branches:

Keep the original character: Process it normally - either add to current partition or start a new one
Try changing it (if not changed yet): Try all 26 possible characters and take the maximum result

The brilliance is that once we compute dp(5, 0b101010, false), we never need to compute it again - just look it up in the memo table.

The Bug That Almost Got Me

My first DP implementation returned:

Wrong Answer
Output: 2
Expected: 3

For input “accca” with k=2, I was getting 2 partitions instead of 3. The problem? I forgot that the DP function returns the number of additional partitions created from position i onward, but doesn’t count the initial partition we’re already in.

The fix was simple but crucial:

return 1 + dp(0, 0, false);  // Add 1 for the first partition

What Makes This Solution Fast?

Several optimizations work together:

Bitmask for character tracking: Using mask & (1 << c) to check if character c is present is incredibly fast - single CPU instruction. __builtin_popcount(mask) counts set bits in hardware.

Efficient memoization key: Packing three state variables into a single 64-bit integer means fast hashing and lookup. The key generation ((long long)i << 27) | ((long long)mask << 1) | changed is just a few bit operations.

Pruning: The changed flag ensures we only explore the “change character” branch once in any path through the recursion tree, cutting the state space significantly.

Early termination: Cached results short-circuit entire subtrees of computation.

The complexity is approximately O(n × 2²⁶ × 2) in the worst case, but in practice the memo table fills much more sparsely because many states are unreachable. Most importantly, each unique state is only computed once.

Lessons Learned

Start simple, then optimize: My naive solution was correct but slow. That’s actually good! I could verify correctness on small inputs before optimizing.

Recognize patterns: The moment I saw “try different choices at each position” + “large input”, I should have thought DP immediately.

State representation matters: Efficiently packing state into a single integer for memoization keys made a huge difference in performance.

Count your partitions carefully: Off-by-one errors in counting problems are insidious. Always verify edge cases.

The final solution passed all 277 test cases with plenty of time to spare. From compilation error to Time Limit Exceeded to Wrong Answer to Accepted - a typical day in competitive programming. this is the result of my final code:

Maximize Partitions After Operations

if you want to solve this question your way, just click here

make sure to share your results with me in email ali@neox1de.com or telegram t.me/neox1de_moharami. I’m happy to learn new things everyday :)

Solving LeetCode's "Maximize Partitions After Operations"

Published October 17, 2025