You are given a string s and an integer k. First, you are allowed to change at most one index in s to another lowercase English letter. After that, do the following partitioning operation until s is empty: Choose the longest prefix of s containing

maxPartitionsAfterOperations.js

/**
 * Calculates the maximum number of partitions after performing operations
 * that allow up to `k` distinct characters per partition.
 *
 * @param {string} s - Input string consisting of lowercase letters.
 * @param {number} k - Maximum number of distinct characters allowed per partition.
 * @return {number} - Maximum number of partitions achievable.
 */
var maxPartitionsAfterOperations = function(s, k) {
    const n = s.length;

    // L[i] stores [leftPartitions, leftMask, leftCount] for prefix ending at i
    const L = Array.from({ length: n }, () => [0, 0, 0]);

    // R[i] stores [rightPartitions, rightMask, rightCount] for suffix starting at i
    const R = Array.from({ length: n }, () => [0, 0, 0]);

    // Build prefix partition info from left to right
    let leftPartitions = 0, leftMask = 0, leftCount = 0;
    for (let i = 0; i < n - 1; i++) {
        const charBit = 1 << (s.charCodeAt(i) - 97); // Bitmask for current character

        if (!(leftMask & charBit)) {
            leftCount++;
            if (leftCount <= k) {
                leftMask |= charBit;
            } else {
                leftPartitions++;
                leftMask = charBit;
                leftCount = 1;
            }
        }
        L[i + 1] = [leftPartitions, leftMask, leftCount];
    }

    // Build suffix partition info from right to left
    let rightPartitions = 0, rightMask = 0, rightCount = 0;
    for (let i = n - 1; i > 0; i--) {
        const charBit = 1 << (s.charCodeAt(i) - 97); // Bitmask for current character

        if (!(rightMask & charBit)) {
            rightCount++;
            if (rightCount <= k) {
                rightMask |= charBit;
            } else {
                rightPartitions++;
                rightMask = charBit;
                rightCount = 1;
            }
        }
        R[i - 1] = [rightPartitions, rightMask, rightCount];
    }

    // Evaluate maximum partitions by checking each split point
    let maxPartitions = 0;
    for (let i = 0; i < n; i++) {
        // Base partition count: left + right + 2 (for current split)
        let partitions = L[i][0] + R[i][0] + 2;

        // Combine masks to count distinct characters at split
        const combinedMask = L[i][1] | R[i][1];
        const distinctCount = combinedMask.toString(2).split('1').length - 1;

        // Adjust partition count based on overlap and k constraint
        if (L[i][2] === k && R[i][2] === k && distinctCount < 26) {
            partitions += 1;
        } else if (Math.min(distinctCount + 1, 26) <= k) {
            partitions -= 1;
        }

        maxPartitions = Math.max(maxPartitions, partitions);
    }

    return maxPartitions;
};