prune by only taking at most n/k chars, each frequency at most f[c] / k
Approach
great speed up: don't build subsequence further if current is not k-repeating (300ms to 90ms)
another way is BFS, explore new length layer by layer (Rust code, no pruning optimizations)
Complexity
Time complexity: $$O(n^r)$$ r = max_freq[a..z] / k
Space complexity: $$O(r)$$ recursion depth
Code
// 91ms
fun longestSubsequenceRepeatedK(s: String, k: Int): String {
var res = ""; val f = IntArray(26); for (c in s) ++f[c - 'a']
val cnt = IntArray(26); val seq = CharArray(s.length / k); var sz = 0
fun check() {
var i = 0; var fr = if (sz > 0) 0 else k
if (sz > 0) for (c in s) if (c == seq[i % sz]) if (++i % sz == 0) fr++
if (fr < k) return
if (sz > res.length) res = String(seq, 0, sz)
for (c in 25 downTo 0) if (f[c] >= k && cnt[c] < f[c] / k) {
++cnt[c]; seq[sz++] = 'a' + c
check()
--cnt[c]; --sz
}
}
check()
return res
}
// 416ms
pub fn longest_subsequence_repeated_k(s: String, k: i32) -> String {
let (mut q, mut q1, mut res) = (vec![String::from("")], vec![], "".into());
while q.len() > 0 {
for sub in &q {
for c in 'a'..='z' {
let next = format!("{}{}", sub.clone(), c);
let mut i = 0; let mut r = next.len() * (k as usize);
for c in s.bytes() {
if c == next.as_bytes()[i % next.len()] {
i += 1; if i == r { break }}}
if i == r { res = next.clone(); q1.push(next) }
}}
(q, q1) = (q1, q); q1.clear()
} res
}
// 92ms
string longestSubsequenceRepeatedK(string s, int k) {
int f[26] = {}, c[26] = {}; for (char x : s) f[x - 'a']++;
string res, seq;
auto dfs = [&](this const auto& dfs) {
int sz = seq.size(), i = 0, cnt = sz ? 0 : k;
if (sz)
for (char x : s)
if (x == seq[i % sz] && ++i % sz == 0)
if (++cnt == k) break;
if (cnt < k) return;
if (sz > (int)res.size()) res = seq;
for (int x = 25; x >= 0; x--) {
if (f[x] >= k && c[x] < f[x] / k) {
c[x]++; seq.push_back('a' + x);
dfs();
seq.pop_back(); c[x]--;
}
}
};
dfs();
return res;
}
