Problem statement

https://leetcode.com/problems/longest-subsequence-repeated-k-times/

Solution

The key to solve this problem is to look carefuly on the constraints: 2 <= n < k * 8. This constrait looks very strange, let us understand what does it mean? In fact it means, that k > n/8, which means that we can have no more than 7 elements in our answer. Why we can not have 8 or more? Because then we just do not have enought symbols: if we take 8 symbols with frequency k, in total we take >= 8*k > n symbols. So, what we need to do is the following:

  1. Take so-called hot symbols only: such that that have frequency k at least. Notice that if we have frequency [k, 2k) we take one symbol, if we are in [2k, 3k) we can take at most 2 and so on.
  2. Generate every possible candidate for substring we can have: for example for hot = "abb", we have the following canditates: ["", a, b, ab, ba, bb, abb, bab, bba]. Notice that we need to create all possible combinations and for each combination we create all permutations.
  3. Finally, sort all candidates starting with longest ones and if we have the same length, with the lexicographically largest and then for each candidate check if we have it k times in our string s.

Complexity

This is the most interesting part for me and why it works. We have k <= 2000 and n < 8*k = 16000. How many possible candidates we can have? I state here without proof that biggest number of candidates is when we have the case of hot having all different symbols, like abcdefg. For this case we have exaclty m = 13700 ~= O(7!) candidates. What is the time to process one candidate? It is O(n), so in total we have O(n * m) time complexity, which is pretty big, so why does it work? The answer is fast python strings and optimized isSubsequence() function. In fact there will be a lot of early stoppings. Space complexity is O(m). I am wondering if you can do the same logic in other languages and get AC, let me know in comments.

Code

class Solution:
    def isSubsequence(self, s, t):
        t = iter(t)
        return all(c in t for c in s)

    def longestSubsequenceRepeatedK(self, s, k):
        hot = "".join(el*(freq//k) for el, freq in Counter(s).items())
            
        combs = set()
        for l in range(len(hot) + 1):
            for cand in combinations(hot, l):
                for perm in permutations(cand):
                    combs.add("".join(perm))

        combs = sorted(combs, key = lambda x: (len(x), x), reverse = True)
        for c in combs:
            if self.isSubsequence(c*k, s):
                return c

If you have any questions, feel free to ask. If you like solution and explanations, please Upvote!