aboutsummaryrefslogtreecommitdiff
path: root/longest_subseq_repeat_k_time.py
blob: 2f4b52520c06387b6e15ee3cc454fe59d7352160 (plain)
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))