3003. Maximize the Number of Partitions After Operations

Description

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.

 

Example 1:

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:

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:

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 <= 104
• s consists only of lowercase English letters.
• 1 <= k <= 26

Solutions

Solution 1: Memoized Search

We design a function \(\textit{dfs}(i, \textit{cur}, t)\) that represents the maximum number of partitions we can obtain when currently processing index \(i\) of string \(s\), the current prefix already contains the character set \(\textit{cur}\), and we can still modify \(t\) characters. Then the answer is \(\textit{dfs}(0, 0, 1)\).

The execution logic of function \(\textit{dfs}(i, \textit{cur}, t)\) is as follows:

1. If \(i \geq n\), it means we have finished processing string \(s\), return 1.
2. Calculate the bitmask \(v = 1 \ll (s[i] - 'a')\) corresponding to the current character \(s[i]\), and calculate the updated character set \(\textit{nxt} = \textit{cur} \mid v\).
3. If the number of bits in \(\textit{nxt}\) exceeds \(k\), it means the current prefix already contains more than \(k\) distinct characters. We need to make a partition, increment the partition count by 1, and recursively call \(\textit{dfs}(i + 1, v, t)\). Otherwise, continue recursively calling \(\textit{dfs}(i + 1, \textit{nxt}, t)\).
4. If \(t > 0\), it means we can still modify a character once. We try to change the current character \(s[i]\) to any lowercase letter (26 choices in total). For each choice, calculate the updated character set \(\textit{nxt} = \textit{cur} \mid (1 \ll j)\), and based on whether it exceeds \(k\) distinct characters, choose the corresponding recursive call method to update the maximum partition count.
5. Use a hash table to cache already computed states to avoid redundant calculations.

The time complexity is \(O(n \times |\Sigma| \times k)\) and the space complexity is \(O(n \times |\Sigma| \times k)\), where \(n\) is the length of string \(s\), and \(|\Sigma|\) is the size of the character set.

Python3JavaC++GoTypeScript

class Solution:
    def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
        @cache
        def dfs(i: int, cur: int, t: int) -> int:
            if i >= n:
                return 1
            v = 1 << (ord(s[i]) - ord("a"))
            nxt = cur | v
            if nxt.bit_count() > k:
                ans = dfs(i + 1, v, t) + 1
            else:
                ans = dfs(i + 1, nxt, t)
            if t:
                for j in range(26):
                    nxt = cur | (1 << j)
                    if nxt.bit_count() > k:
                        ans = max(ans, dfs(i + 1, 1 << j, 0) + 1)
                    else:
                        ans = max(ans, dfs(i + 1, nxt, 0))
            return ans

        n = len(s)
        return dfs(0, 0, 1)

class Solution {
    private Map<List<Integer>, Integer> f = new HashMap<>();
    private String s;
    private int k;

    public int maxPartitionsAfterOperations(String s, int k) {
        this.s = s;
        this.k = k;
        return dfs(0, 0, 1);
    }

    private int dfs(int i, int cur, int t) {
        if (i >= s.length()) {
            return 1;
        }
        var key = List.of(i, cur, t);
        if (f.containsKey(key)) {
            return f.get(key);
        }
        int v = 1 << (s.charAt(i) - 'a');
        int nxt = cur | v;
        int ans = Integer.bitCount(nxt) > k ? dfs(i + 1, v, t) + 1 : dfs(i + 1, nxt, t);
        if (t > 0) {
            for (int j = 0; j < 26; ++j) {
                nxt = cur | (1 << j);
                if (Integer.bitCount(nxt) > k) {
                    ans = Math.max(ans, dfs(i + 1, 1 << j, 0) + 1);
                } else {
                    ans = Math.max(ans, dfs(i + 1, nxt, 0));
                }
            }
        }
        f.put(key, ans);
        return ans;
    }
}

class Solution {
public:
    int maxPartitionsAfterOperations(string s, int k) {
        int n = s.size();
        unordered_map<long long, int> f;
        auto dfs = [&](this auto&& dfs, int i, int cur, int t) -> int {
            if (i >= n) {
                return 1;
            }
            long long key = (long long) i << 32 | cur << 1 | t;
            if (f.count(key)) {
                return f[key];
            }
            int v = 1 << (s[i] - 'a');
            int nxt = cur | v;
            int ans = __builtin_popcount(nxt) > k ? dfs(i + 1, v, t) + 1 : dfs(i + 1, nxt, t);
            if (t) {
                for (int j = 0; j < 26; ++j) {
                    nxt = cur | (1 << j);
                    if (__builtin_popcount(nxt) > k) {
                        ans = max(ans, dfs(i + 1, 1 << j, 0) + 1);
                    } else {
                        ans = max(ans, dfs(i + 1, nxt, 0));
                    }
                }
            }
            return f[key] = ans;
        };
        return dfs(0, 0, 1);
    }
};

func maxPartitionsAfterOperations(s string, k int) int {
    n := len(s)
    type tuple struct{ i, cur, t int }
    f := map[tuple]int{}
    var dfs func(i, cur, t int) int
    dfs = func(i, cur, t int) int {
        if i >= n {
            return 1
        }
        key := tuple{i, cur, t}
        if v, ok := f[key]; ok {
            return v
        }
        v := 1 << (s[i] - 'a')
        nxt := cur | v
        var ans int
        if bits.OnesCount(uint(nxt)) > k {
            ans = dfs(i+1, v, t) + 1
        } else {
            ans = dfs(i+1, nxt, t)
        }
        if t > 0 {
            for j := 0; j < 26; j++ {
                nxt = cur | (1 << j)
                if bits.OnesCount(uint(nxt)) > k {
                    ans = max(ans, dfs(i+1, 1<<j, 0)+1)
                } else {
                    ans = max(ans, dfs(i+1, nxt, 0))
                }
            }
        }
        f[key] = ans
        return ans
    }
    return dfs(0, 0, 1)
}

function maxPartitionsAfterOperations(s: string, k: number): number {
    const n = s.length;
    const f: Map<bigint, number> = new Map();
    const dfs = (i: number, cur: number, t: number): number => {
        if (i >= n) {
            return 1;
        }
        const key = (BigInt(i) << 27n) | (BigInt(cur) << 1n) | BigInt(t);
        if (f.has(key)) {
            return f.get(key)!;
        }
        const v = 1 << (s.charCodeAt(i) - 97);
        let nxt = cur | v;
        let ans = 0;
        if (bitCount(nxt) > k) {
            ans = dfs(i + 1, v, t) + 1;
        } else {
            ans = dfs(i + 1, nxt, t);
        }
        if (t) {
            for (let j = 0; j < 26; ++j) {
                nxt = cur | (1 << j);
                if (bitCount(nxt) > k) {
                    ans = Math.max(ans, dfs(i + 1, 1 << j, 0) + 1);
                } else {
                    ans = Math.max(ans, dfs(i + 1, nxt, 0));
                }
            }
        }
        f.set(key, ans);
        return ans;
    };
    return dfs(0, 0, 1);
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

Comments