# 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))