Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

After choosing the possible replacement, partition boundaries are forced: extend the current prefix until adding a character would introduce more than k distinct letters. A state therefore needs the current position, the current partition's letter mask, and whether the one allowed change has already been used.

Approach

At each position, try keeping its character. If the replacement is still available, also try changing it. Add the chosen letter to the mask. If the distinct-letter count exceeds k, count a completed partition and start a new mask containing only that letter; otherwise extend the current partition.

Python memoizes the maximum remaining partition count and returns one at the end for the last partition. Its candidate replacements are the letters occurring in the string plus one absent letter: all absent letters behave identically because only one position can change. JavaScript tries all 26 letters and keeps the best completed-partition count per state while scanning forward, then adds the last partition. Its k = 26 shortcut returns one. Keeping the original character throughout also covers making no change.

class Solution:
    def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
        u = {ord(c) - ord('a') for c in s}
        for i in range(26): 
            if not i in u:
                u.add(i)
                break

        @cache
        def dp(mask, change, i):
            if i == len(s): return 1

            best = 0
            
            # continue with curr char
            curr = ord(s[i]) - ord('a')
            nmask = mask | (1 << curr)
            if nmask.bit_count() <= k: best = max(best, dp(nmask, change, i + 1))
            else: best = max(best, dp(1 << curr, change, i + 1) + 1)
            
            # try new char
            if not change:
                for j in u:
                    if j == curr: continue
                    nmask = mask | (1 << j)
                    if nmask.bit_count() <= k: best = max(best, dp(nmask, True, i + 1))
                    else: best = max(best, dp(1 << j, True, i + 1) + 1)
            
            return best
        
        return dp(0, False, 0)

Complexity analysis

Let n = s.length and M = sum(C(26, i), i = 0..k), an upper bound on possible current-partition masks. A conservative worst-case bound is O(26nM) time and O(n*M) auxiliary space for both versions, treating the fixed 26-bit operations as constant-time. Python memoizes states and has O(n) recursive depth, which can exceed an unadjusted recursion limit. JavaScript retains every layer in its layers array, so its space is not just one rolling layer; its k = 26 shortcut instead takes O(1) time and space.