| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
Hard |
3039 |
Weekly Contest 379 Q4 |
|
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
scontaining at mostkdistinct characters. - Delete the prefix from
sand increase the number of partitions by one. The remaining characters (if any) insmaintain 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:
- The longest prefix containing at most 2 distinct characters is
"ac", we remove it andsbecomes"bca". - Now The longest prefix containing at most 2 distinct characters is
"bc", so we remove it andsbecomes"a". - Finally, we remove
"a"andsbecomes 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 <= 104sconsists only of lowercase English letters.1 <= k <= 26
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;
function<int(int, int, int)> dfs = [&](int i, int cur, int t) {
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;
}