Problem

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 at most k distinct characters.
  • Delete the prefix from s and increase the number of partitions by one. The remaining characters (if any) in s maintain their initial order.

Return an integer denoting the maximum number of resulting partitions after the operations by optimally choosing at most one index to change.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


Input: s = "accca", k = 2

Output: 3

Explanation:

The optimal way is to change `s[2]` to something other than a and c, for
example, b. then it becomes `"acbca"`.

Then we perform the operations:

  1. The longest prefix containing at most 2 distinct characters is `"ac"`, we remove it and `s` becomes `"bca"`.
  2. Now The longest prefix containing at most 2 distinct characters is `"bc"`, so we remove it and `s` becomes `"a"`.
  3. Finally, we remove `"a"` and `s` becomes empty, so the procedure ends.

Doing the operations, the string is divided into 3 partitions, so the answer
is 3.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Input: s = "aabaab", k = 3

Output: 1

Explanation:

Initially `s` contains 2 distinct characters, so whichever character we
change, it will contain at most 3 distinct characters, so the longest prefix
with at most 3 distinct characters would always be all of it, therefore the
answer is 1.

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


Input: s = "xxyz", k = 1

Output: 4

Explanation:

The optimal way is to change `s[0]` or `s[1]` to something other than
characters in `s`, for example, to change `s[0]` to `w`.

Then `s` becomes `"wxyz"`, which consists of 4 distinct characters, so as `k`
is 1, it will divide into 4 partitions.

Constraints

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

Solution

Method 1 – Greedy Partitioning with One Change Simulation

Intuition

To maximize the number of partitions, we want to maximize the number of times we can take a prefix with at most k distinct characters. By changing at most one character, we can try all possible single-character changes and simulate the partitioning process for each, taking the maximum result.

Approach

  1. For each index in s, try changing it to every possible lowercase letter (other than the current one).
  2. For each modified string, simulate the partitioning process:
    • Start from the beginning, greedily take the longest prefix with at most k distinct characters, remove it, and repeat.
    • Count the number of partitions.
  3. Also consider the case where no change is made.
  4. Return the maximum number of partitions found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    int maxPartitionsAfterChange(string s, int k) {
        int n = s.size(), ans = 0;
        auto getPartitions = [&](string t) {
            int cnt = 0, l = 0;
            while (l < n) {
                unordered_set<char> st;
                int r = l;
                while (r < n && (st.count(t[r]) || st.size() < k)) {
                    st.insert(t[r]);
                    r++;
                }
                cnt++;
                l = r;
            }
            return cnt;
        };
        ans = getPartitions(s);
        for (int i = 0; i < n; ++i) {
            for (char c = 'a'; c <= 'z'; ++c) {
                if (c == s[i]) continue;
                string t = s;
                t[i] = c;
                ans = max(ans, getPartitions(t));
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public int maxPartitionsAfterChange(String s, int k) {
        int n = s.length(), ans = 0;
        ans = getPartitions(s, k);
        for (int i = 0; i < n; i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == s.charAt(i)) continue;
                StringBuilder t = new StringBuilder(s);
                t.setCharAt(i, c);
                ans = Math.max(ans, getPartitions(t.toString(), k));
            }
        }
        return ans;
    }
    private int getPartitions(String s, int k) {
        int n = s.length(), cnt = 0, l = 0;
        while (l < n) {
            Set<Character> st = new HashSet<>();
            int r = l;
            while (r < n && (st.contains(s.charAt(r)) || st.size() < k)) {
                st.add(s.charAt(r));
                r++;
            }
            cnt++;
            l = r;
        }
        return cnt;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def maxPartitionsAfterChange(self, s: str, k: int) -> int:
        def get_partitions(t: str) -> int:
            n = len(t)
            cnt = 0
            l = 0
            while l < n:
                st = set()
                r = l
                while r < n and (t[r] in st or len(st) < k):
                    st.add(t[r])
                    r += 1
                cnt += 1
                l = r
            return cnt
        ans = get_partitions(s)
        n = len(s)
        for i in range(n):
            for c in map(chr, range(97, 123)):
                if c == s[i]:
                    continue
                t = s[:i] + c + s[i+1:]
                ans = max(ans, get_partitions(t))
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

impl Solution {
    pub fn max_partitions_after_change(s: String, k: i32) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let mut ans = get_partitions(s, k);
        for i in 0..n {
            for c in b'a'..=b'z' {
                if c == s[i] { continue; }
                let mut t = s.to_vec();
                t[i] = c;
                ans = ans.max(get_partitions(&t, k));
            }
        }
        ans
    }
}
fn get_partitions(s: &[u8], k: i32) -> i32 {
    let n = s.len();
    let mut cnt = 0;
    let mut l = 0;
    while l < n {
        let mut st = std::collections::HashSet::new();
        let mut r = l;
        while r < n && (st.contains(&s[r]) || st.len() < k as usize) {
            st.insert(s[r]);
            r += 1;
        }
        cnt += 1;
        l = r;
    }
    cnt
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    maxPartitionsAfterChange(s: string, k: number): number {
        function getPartitions(t: string): number {
            let n = t.length, cnt = 0, l = 0;
            while (l < n) {
                const st = new Set<string>();
                let r = l;
                while (r < n && (st.has(t[r]) || st.size < k)) {
                    st.add(t[r]);
                    r++;
                }
                cnt++;
                l = r;
            }
            return cnt;
        }
        let ans = getPartitions(s);
        for (let i = 0; i < s.length; i++) {
            for (let c = 97; c <= 122; c++) {
                const ch = String.fromCharCode(c);
                if (ch === s[i]) continue;
                const t = s.slice(0, i) + ch + s.slice(i+1);
                ans = Math.max(ans, getPartitions(t));
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * 26 * n) — for each index and each letter, we simulate the partitioning process.
  • 🧺 Space complexity: O(n) — for temporary strings and sets.