Problem statement

You are given a string s and an integer k. You split s with the following process until it is empty:

• Remove the longest prefix of s that contains at most k distinct characters. That prefix counts as one partition.

Before you start, you may change at most one character of s to any lowercase English letter.

Return the maximum number of partitions you can get with an optimal choice of that change.

Example 1

Input: s = "accca", k = 2
Output: 3
Explanation: Change s[2] to 'b' to get "acbca". The prefixes taken are "ac", "bc" and "a": 3 partitions.

Example 2

Input: s = "aabaab", k = 3
Output: 1
Explanation: Only two distinct letters exist and one change adds at most one more, so the whole string is always one partition.

Example 3

Input: s = "xxyz", k = 1
Output: 4
Explanation: Change s[1] to 'a': "xayz" splits into "x", "a", "y", "z".

Constraints

• 1 <= s.length <= 10^4
• s consists only of lowercase English letters
• 1 <= k <= 26

Hints for Maximize the Number of Partitions After Operations

1. Hint 1

   Without a change, the split is fixed by a left-to-right greedy. A change at index i leaves everything before i exactly as it was.

2. Hint 2

   Precompute, for every suffix start j, how many partitions the greedy makes on s[j..] when a fresh partition starts at j.

3. Hint 3

   When you change s[i] to c, simulate only the partition that contains index i: from the greedy state before i (partitions closed, letter set of the open one), add c, then extend through s[i+1..] until a (k+1)-th distinct letter appears. Past that point the rest is a fresh suffix you already counted. Using the order in which letters first appear after i, the extension takes O(26).

How to solve Maximize the Number of Partitions After Operations

A single change splits the string into three zones: an untouched prefix (whose greedy state is known), the one partition that contains the changed index, and an untouched suffix that starts a fresh partition — whose count can be precomputed for every start position.

Approach

1. For every j, record next[j][c] (first index ≥ j holding letter c) and order[j], the letters of s[j..] in order of first appearance.
2. fresh[j] = partitions of s[j..] from a fresh start: the open partition ends right before the (k+1)-th letter of order[j], at index e, so fresh[j] = 1 + fresh[e] (with fresh[n] = 0).
3. Walk i from left to right keeping the greedy state before i: done closed partitions and the letter set mask of the open one.
4. For every letter c: if c is already in mask or mask has fewer than k letters, add it; otherwise close the partition (done + 1) and open {c}. Then scan order[i+1], counting letters not in the set; the first one that pushes the count above k sits at e = next[i+1][that letter]. The total is done' + 1 + fresh[e] (fresh[n] = 0 if no such letter).
5. Advance the state with the original s[i]. The answer is the best total seen, including fresh[0] (no change).

Why it works

The greedy only looks forward, so characters before i behave identically with or without the change, and once a partition boundary appears after i, the remaining string is untouched and starts fresh — exactly fresh[e]. Inside the open partition, a letter extends it unless it is new and the set is full; scanning letters in order of first appearance finds the first such position, because positions between first appearances repeat letters already counted.

Complexity

• Time — O(26 · 26 · n)
• Space — O(26 · n)

Pitfalls

• Changing to the same letter (no change) must also be considered — it is covered by trying every c.
• With k = 26 nothing can ever be split; the answer is 1.
• When the changed letter closes the current partition, the new partition starts at i, not after it.

Reference solution

Python

def maxPartitionsAfterOperations(s: str, k: int) -> int:
    n = len(s)
    a = [ord(c) - 97 for c in s]
    nxt = [None] * (n + 1)
    nxt[n] = [n] * 26
    order = [None] * (n + 1)
    order[n] = []
    for i in range(n - 1, -1, -1):
        row = nxt[i + 1][:]
        row[a[i]] = i
        nxt[i] = row
        order[i] = [a[i]] + [c for c in order[i + 1] if c != a[i]]
    fresh = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        e = nxt[i][order[i][k]] if len(order[i]) > k else n
        fresh[i] = 1 + fresh[e]
    best = fresh[0]
    done, mask, size = 0, 0, 0
    for i in range(n):
        for c in range(26):
            d2, m2, z2 = done, mask, size
            if (m2 >> c) & 1:
                pass
            elif z2 < k:
                m2 |= 1 << c
                z2 += 1
            else:
                d2 += 1
                m2 = 1 << c
                z2 = 1
            e = n
            for ch in order[i + 1]:
                if not (m2 >> ch) & 1:
                    z2 += 1
                    if z2 > k:
                        e = nxt[i + 1][ch]
                        break
            total = d2 + 1 + fresh[e]
            if total > best:
                best = total
        c = a[i]
        if (mask >> c) & 1:
            pass
        elif size < k:
            mask |= 1 << c
            size += 1
        else:
            done += 1
            mask = 1 << c
            size = 1
    return best

Java

public static int maxPartitionsAfterOperations(String s, int k) {
    int n = s.length();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) a[i] = s.charAt(i) - 'a';
    // nxt[i][c]: first index >= i holding c; order[i]: letters of s[i..] by first appearance
    int[][] nxt = new int[n + 1][26];
    int[][] order = new int[n + 1][26];
    int[] olen = new int[n + 1];
    Arrays.fill(nxt[n], n);
    for (int i = n - 1; i >= 0; i--) {
        nxt[i] = nxt[i + 1].clone();
        nxt[i][a[i]] = i;
        order[i][olen[i]++] = a[i];
        for (int t = 0; t < olen[i + 1]; t++) if (order[i + 1][t] != a[i]) order[i][olen[i]++] = order[i + 1][t];
    }
    int[] fresh = new int[n + 1];
    for (int i = n - 1; i >= 0; i--) {
        int e = olen[i] > k ? nxt[i][order[i][k]] : n;
        fresh[i] = 1 + fresh[e];
    }
    int best = fresh[0], done = 0, mask = 0, size = 0;
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            int d2 = done, m2 = mask, z2 = size;
            if (((m2 >> c) & 1) == 0) {
                if (z2 < k) { m2 |= 1 << c; z2++; }
                else { d2++; m2 = 1 << c; z2 = 1; }
            }
            int e = n;
            for (int t = 0; t < olen[i + 1]; t++) {
                int ch = order[i + 1][t];
                if (((m2 >> ch) & 1) == 0 && ++z2 > k) { e = nxt[i + 1][ch]; break; }
            }
            best = Math.max(best, d2 + 1 + fresh[e]);
        }
        int c = a[i];
        if (((mask >> c) & 1) == 0) {
            if (size < k) { mask |= 1 << c; size++; }
            else { done++; mask = 1 << c; size = 1; }
        }
    }
    return best;
}

C++

int maxPartitionsAfterOperations(string s, int k) {
    int n = s.size();
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = s[i] - 'a';
    // nxt[i][c]: first index >= i holding c; order[i]: letters of s[i..] by first appearance
    vector<array<int, 26>> nxt(n + 1), order(n + 1);
    vector<int> olen(n + 1, 0);
    nxt[n].fill(n);
    for (int i = n - 1; i >= 0; i--) {
        nxt[i] = nxt[i + 1];
        nxt[i][a[i]] = i;
        order[i][olen[i]++] = a[i];
        for (int t = 0; t < olen[i + 1]; t++) if (order[i + 1][t] != a[i]) order[i][olen[i]++] = order[i + 1][t];
    }
    vector<int> fresh(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) {
        int e = olen[i] > k ? nxt[i][order[i][k]] : n;
        fresh[i] = 1 + fresh[e];
    }
    int best = fresh[0], done = 0, mask = 0, size = 0;
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            int d2 = done, m2 = mask, z2 = size;
            if (!((m2 >> c) & 1)) {
                if (z2 < k) { m2 |= 1 << c; z2++; }
                else { d2++; m2 = 1 << c; z2 = 1; }
            }
            int e = n;
            for (int t = 0; t < olen[i + 1]; t++) {
                int ch = order[i + 1][t];
                if (!((m2 >> ch) & 1) && ++z2 > k) { e = nxt[i + 1][ch]; break; }
            }
            best = max(best, d2 + 1 + fresh[e]);
        }
        int c = a[i];
        if (!((mask >> c) & 1)) {
            if (size < k) { mask |= 1 << c; size++; }
            else { done++; mask = 1 << c; size = 1; }
        }
    }
    return best;
}

JavaScript

var maxPartitionsAfterOperations = function(s, k) {
    var n = s.length, i, c;
    var a = new Array(n);
    for (i = 0; i < n; i++) a[i] = s.charCodeAt(i) - 97;
    // nxt[i*26+c]: first index >= i holding c; order[i]: letters of s[i..] by first appearance
    var nxt = new Array((n + 1) * 26).fill(n);
    var order = new Array(n + 1);
    order[n] = [];
    for (i = n - 1; i >= 0; i--) {
        for (c = 0; c < 26; c++) nxt[i * 26 + c] = nxt[(i + 1) * 26 + c];
        nxt[i * 26 + a[i]] = i;
        var o = [a[i]];
        for (var t = 0; t < order[i + 1].length; t++) if (order[i + 1][t] !== a[i]) o.push(order[i + 1][t]);
        order[i] = o;
    }
    var fresh = new Array(n + 1).fill(0);
    for (i = n - 1; i >= 0; i--) {
        var e0 = order[i].length > k ? nxt[i * 26 + order[i][k]] : n;
        fresh[i] = 1 + fresh[e0];
    }
    var best = fresh[0], done = 0, mask = 0, size = 0;
    for (i = 0; i < n; i++) {
        for (c = 0; c < 26; c++) {
            var d2 = done, m2 = mask, z2 = size;
            if ((m2 >> c) & 1) {
                // already in the open partition
            } else if (z2 < k) { m2 |= 1 << c; z2++; }
            else { d2++; m2 = 1 << c; z2 = 1; }
            var e = n, ord = order[i + 1];
            for (var t = 0; t < ord.length; t++) {
                if (!((m2 >> ord[t]) & 1)) {
                    z2++;
                    if (z2 > k) { e = nxt[(i + 1) * 26 + ord[t]]; break; }
                }
            }
            if (d2 + 1 + fresh[e] > best) best = d2 + 1 + fresh[e];
        }
        c = a[i];
        if ((mask >> c) & 1) {
            // unchanged
        } else if (size < k) { mask |= 1 << c; size++; }
        else { done++; mask = 1 << c; size = 1; }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Prefix and Suffix Search Hard
• Recover a Tree From Preorder Traversal Hard
• Minimum Time to Revert Word to Initial State II Hard
• Maximum Product of the Length of Two Palindromic Substrings Hard
• Longest Chunked Palindrome Decomposition Hard
• K-Similar Strings Hard