aboutsummaryrefslogtreecommitdiff
path: root/longest_subseq_repeat_k_time.py
diff options
context:
space:
mode:
Diffstat (limited to 'longest_subseq_repeat_k_time.py')
-rw-r--r--longest_subseq_repeat_k_time.py45
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))