ways to remove duplicates, preserve length at least k #hard #dp
Intuition
Didn't solved.
// aaabbb k=3 len=6
// aaabbb
//
// aaabb b=3, 3-1=2, 6-2=4
// aaab
// aabbb a:2, 6-2=4
// abbb
//
// aabb combinatorics? a_variants * b_variants - bad_comb
// aab
// abb
//
// bad:
// ab
// dp? it is 10^5 * 2000 will give TLE, use hint(14 minute)
// at most k - 1
// bad combination length is at most k - 1
// ab - single bad
// if k=5
// ab, abb, abbb, aab, aabb, aaab - bad
// how to count them?
// aaabbbcccbbb k=7
// a b c b min=4, can take +2 on each or +1 +1 on any pair
// aa
// aaa
// aa bb
// aa cc
// aa bb
// bb
// bbb
//(aa bb)
// bb cc
// bb bb
// cc
// ccc
//(aa cc)
// (bb cc)
// cc bb
// bb
// bbb
//(aa bb)
// (bb bb)
// (cc bb) (15 bad), total=1*3a*3b*3c*3b = 9*9=81
// ans = 81-15 = 66
// choose up to 2 from aa|bb|cc|bb = choose 1 + choose 2
// C(1, 4) + C(2, 4) ??? how to choose from: a|bbbb|cc
// choose (k - 1 - min) from islands a|bbb|cc|b|aa
// only non-singles
// bb|c|a
// 43 minute, look for solution
the main hardness is how to choose bad variants from a non-equal buckets (after we remove all the minimal required chars)
n - size of minimum non-repeating buckets
g - groups, with filtered out minimal required values aa becomes a, b becomes `` and filtered out; we only interested in the repeating_count - 1 values to choose from
use DP[curr_bucket] = sum_{kk-g(i)}(DP[prev_bucket]) = PS[curr]-PS[kk-g(i)]
// 416ms
fun possibleStringCount(w: String, k: Int): Int {
val M = 1_000_000_007L; val g = ArrayList<Int>()
var c = 1; var all = 1L; var n = k
for (i in 1..w.length) if (i < w.length && w[i] == w[i - 1]) ++c
else { --n; if (c - 1 > 0) g += c - 1; all = (all * c) % M; c = 1 }
if (n <= 0) return all.toInt()
val dp = Array(2) { LongArray(n) }; dp[0][0] = 1L; val ps = LongArray(n + 1)
for (i in 0..<g.size) for (kk in 0..<n) {
ps[kk + 1] = (ps[kk] + dp[i % 2][kk]) % M
dp[1 - (i % 2)][kk] = (ps[kk + 1] - ps[max(0, kk - g[i])]) % M
}
var bad = 0L; for (i in 0..<n) bad = (bad + dp[g.size % 2][i]) % M
return ((all + M - bad) % M).toInt()
}
// 49ms
pub fn possible_string_count(w: String, k: i32) -> i32 {
let g = w.as_bytes().chunk_by(|a, b| a == b).map(|c| c.len() as i64).collect::<Vec<_>>();
let M = 1_000_000_007; let mut all = 1; for &c in &g { all = (all * c) % M };
if k as usize <= g.len() { return all as i32 }; let n = k as usize - g.len();
let g = g.iter().filter(|&&c| c > 1).map(|&c| c - 1).collect::<Vec<_>>();
let mut dp = vec![vec![0; n]; 2]; dp[0][0] = 1i64; let mut ps = vec![0; n + 1];
for i in 0..g.len() { for kk in 0..n {
ps[kk + 1] = (ps[kk] + dp[i % 2][kk]) % M;
dp[1 - (i % 2)][kk] = (ps[kk + 1] - ps[(0.max(kk as i64 - g[i])) as usize]) % M;
}}
let mut bad = 0; for i in 0..n { bad = (bad + dp[g.len() % 2][i]) % M }
((all + M - bad) % M) as i32
}
