For each position, try to brute-force the replacements.

To speed up the brute-force solution, we can precompute the following (without changing any index) using prefix sums and binary search:<ul> <li><code>pref[i]</code>: The number of resulting partitions from the operations by performing the operations on <code>s[0:i]</code>.</li> <li><code>suff[i]</code>: The number of resulting partitions from the operations by performing the operations on <code>s[i:n - 1]</code>, where <code>n == s.length</code>.</li> <li><code>partition_start[i]</code>: The start index of the partition containing the <code>i^th</code> index after performing the operations.</li> </ul>

Now, for a position <code>i</code>, we can try all possible <code>25</code> replacements:<br /> For a replacement, using prefix sums and binary search, we need to find the rightmost index, <code>r</code>, such that the number of distinct characters in the range <code>[partition_start[i], r]</code> is at most <code>k</code>.<br /> There are <code>2</code> cases:<ul> <li><code>r >= i</code>: the number of resulting partitions in this case is <code>1 + pref[partition_start[i] - 1] + suff[r + 1]</code>.</li> <li>Otherwise, we need to find the rightmost index <code>r₂</code> such that the number of distinct characters in the range <code>[r:r₂]</code> is at most <code>k</code>. The answer in this case is <code>2 + pref[partition_start[i] - 1] + suff[r₂ + 1]</code></li> </ul>

The answer is the maximum among all replacements.