Longest Subsequence Repeated k Times LeetCode solution in Python

1
class Solution:
2
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
3
        n = len(s)
4
        max_chunk_sz = n // k
5

6
        d = collections.Counter(s)
7
        chars = sorted([c for c in d if d[c] >= k], reverse=True)
8
        if not chars:
9
            return ""
10

11
        old_cand = chars
12
        for m in range(2, max_chunk_sz + 1):
13
            new_cand = []
14
            for t in self.get_next_level(old_cand, chars):
15
                if self.find(s, t * k):
16
                    new_cand.append(t)
17

18
            if len(new_cand) == 0:
19
                break
20
            old_cand = new_cand
21
        return old_cand[0]
22

23
    def get_next_level(self, cand, chars):
24
        for s in cand:
25
            for ch in chars:
26
                yield s + ch
27

28
    def find(self, s, t):
29
        # find subsequence t in s
30
        j = 0
31
        for i in range(len(s)):
32
            if s[i] == t[j]:
33
                j += 1
34
            if j == len(t):
35
                return True
36
        return False