1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
# 2014. Longest Subsequence Repeated k Times
from collections import Counter
from itertools import combinations, permutations
"""
you are given a string 's' of length 'n', and an integer 'k. you are tasked
to find the longest subsequence repeated 'k' times in 's'. a subsequence is a
string that can be derived from another string by deleting some or no
characters without changing the order of the remaining characters. a
subsequence 'seq' is repeated 'k' times in a sting 's' if 'seq k' is a
subsequence of 's' where 'seq k' represents a string constructed by
concatenating 'seq' 'k' times. return the longest subsequence repeated 'k'
times in string 's'. if multiple subsequences are found, return the
lexicographically largest one.
"""
class Solution(object):
def is_subseq(self, s, t):
t = iter(t)
return all(i in t for i in s)
def longestSubsequenceRepeatedK(self, s, k):
"""
:type s: str
:type k: int
:rtype: str
"""
freq = "".join(i * (j // k) for i, j in Counter(s).items())
combs = set()
for i in range(len(freq) + 1):
for j in combinations(freq, i):
for l in permutations(j):
combs.add("".join(l))
combs = sorted(combs, key=lambda x: (len(x), x), reverse=True)
for i in combs:
if self.is_subseq(i * k, s):
return i
if __name__ == "__main__":
obj = Solution()
print(obj.longestSubsequenceRepeatedK(s="letsleetcode", k=2))
print(obj.longestSubsequenceRepeatedK(s="bb", k=2))
print(obj.longestSubsequenceRepeatedK(s="ab", k=2))
|