Solving LeetCode's "Maximize Partitions After Operations"

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:

1. Continue current partition: Add current character to mask if it fits
2. Start new partition: Reset mask and continue

The magic happens in the transition. When I have the chance to use my character change operation, I try changing the current character to something that would optimize the partition structure.

The Optimization Insight

The crucial realization was that when changing a character, I should change it to match existing characters in the current partition whenever possible. This maximizes the number of characters I can fit before being forced to start a new partition.

So instead of trying all 26 letters, I:

• If the current partition already has some characters, try changing to one of those
• If the partition is empty, try changing to the next character in the string
• Only when those fail do I consider other options

This reduced the branching factor dramatically.

Final Implementation

The final solution had these key components:

1. Base case: When we reach the end of string, return 0
2. Memoization: Use unordered_map to cache results
3. State transitions: Handle continue partition, start new partition, and character change
4. Optimization: Smart character selection when using the change operation

The time complexity dropped from O(n² × 26) to O(n × 2²⁶) in the worst case, but much better in practice due to the optimization and memoization.

Lessons Learned

• Always check if your code compiles before optimizing - I wasted time on a broken foundation
• Look for overlapping subproblems - if you're recomputing the same states, memoization is probably the answer
• Reduce branching factor - instead of brute forcing all possibilities, think about which choices actually matter
• Bitmask operations are your friend for problems involving sets of small items

The journey from a non-compiling function to an accepted solution taught me more about DP and optimization than any textbook could. Sometimes the best way to learn is by fixing your own mistakes, one by one.

Time to AC: 3 attempts, 2 hours, 1 realization that I should've tested my code locally first!