diff options
Diffstat (limited to 'longest_subseq_repeat_k_time.py')
-rw-r--r-- | longest_subseq_repeat_k_time.py | 45 |
1 files changed, 45 insertions, 0 deletions
diff --git a/longest_subseq_repeat_k_time.py b/longest_subseq_repeat_k_time.py new file mode 100644 index 0000000..2f4b525 --- /dev/null +++ b/longest_subseq_repeat_k_time.py @@ -0,0 +1,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)) |