Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Any character in the answer must appear at least k times in the source. Also, if a candidate repeated k times is not a subsequence, no longer candidate having it as a prefix can succeed. These facts prune a backtracking search over possible answer strings.

Approach

Count characters and discard those appearing fewer than k times from both the candidate alphabet and source scan. Extend the current candidate by each remaining character, checking with a forward subsequence scan whether the extension repeated k times fits. Recurse only on successful extensions. Track the longest valid candidate, choosing the lexicographically larger one on equal lengths. Every valid candidate has length at most floor(sourceLength / k), so extensions eventually stop. Return the best, initially empty.

class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        map = defaultdict(int)
        for c in s:
            map[c] += 1

        candidates = []
        for key, v in map.items():
            if v >= k:
                candidates.append(key)

        s = [x for x in s if map[x] >= k]  # for optimization

        def is_subsequence(target):
            it = iter(s)
            return all(c in it for c in target)
            # j = 0
            # for c in s:
                # if c == target[j]:
                    # j += 1
                    # if j == len(target):
                        # return True
            # return False

        self.res = ''
        def bt(curr):
            if len(curr) > len(self.res):
                self.res = curr
            elif len(curr) == len(self.res) and curr > self.res:
                self.res = curr
            for c in candidates:
                next = curr + c
                if is_subsequence(next * k):
                    bt(next)

        bt('')
        return self.res

Complexity analysis

Let n be the original string length, c the candidate-character count, L = floor(n/k) <= 7, and P the number of valid prefixes explored, including the empty prefix. Preprocessing takes O(n), and each prefix attempts c extensions. If c > 0 then k <= n, so constructing each repeated candidate of length at most k(L + 1) and testing it costs O(n). Total time is O(n(1 + cP)), including O(n) when c = 0. Auxiliary space is O(n + L^2 + c), covering filtering/counts, a temporary repeated candidate and simultaneously live immutable recursive prefixes.