# 27.06.2025 [2014. Longest Subsequence Repeated k Times]

# 27.06.2025
[2014. Longest Subsequence Repeated k Times](https://leetcode.com/problems/longest-subsequence-repeated-k-times/description/) hard
[blog post](https://leetcode.com/problems/longest-subsequence-repeated-k-times/solutions/6890919/kotlin-rust-by-samoylenkodmitry-t5aq/)
[substack](https://open.substack.com/pub/dmitriisamoilenko/p/27062025-2014-longest-subsequence?r=2bam17&utm_campaign=post&utm_medium=web&showWelcomeOnShare=true)
[youtube](https://youtu.be/cqLEjrAWcIQ)
#### Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1032

#### Problem TLDR

Longest k-repeating subsequence #hard #backtracking

#### Intuition

Used the hints.
1. find all `good` characters (at least `k` frequent)
2. do DFS with backtracking
3. 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
https://dmitrysamoylenko.com/2023/07/14/leetcode_daily.html

Видео # 27.06.2025 [2014. Longest Subsequence Repeated k Times] канала KittyCat, Keyboard and LeetCode