Longest Subsequence Repeated K Times - Leetcode Solution

The Longest Subsequence Repeated K Times problem is a LeetCode problem that asks you to find the longest subsequence that can be repeated K times in a given string.

The problem can be solved using a combination of brute force and dynamic programming. The basic idea is to create a frequency table for all the characters in the given string and then use that to find all possible sub-sequences. We then check whether each sub-sequence can be repeated K times or not.

To implement this solution, follow these steps:

Step 1: Create a frequency table of the characters in the string.

Step 2: For each character, create a list of indices where that character appears.

Step 3: Create a list of all possible sub-sequences of the string.

Step 4: For each sub-sequence, check whether it can be repeated K times or not.

Step 5: Return the longest sub-sequence that can be repeated K times.

Here is the Python implementation of the above algorithm:

from collections import Counter

class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        freq = Counter(s)
        char_indices = {char: [] for char in freq.keys()}
        for i, char in enumerate(s):
            char_indices[char].append(i)
        
        sequence_list = []
        n = len(s)
        def generate_subsequences(sub_seq, index):
            if len(sub_seq) == k:
                sequence_list.append(sub_seq)
            else:
                for char, indices in char_indices.items():
                    if not indices:
                        continue
                    if index < indices[-1]:
                        next_index = indices[bisect.bisect_left(indices, index+1)]
                        generate_subsequences(sub_seq+char, next_index)
        
        for char, indices in char_indices.items():
            if not indices:
                continue
            next_index = indices[bisect.bisect_left(indices, -1)]
            generate_subsequences(char, next_index)
        
        longest_subsequence = ""
        for sub_sequence in sequence_list:
            if sub_sequence*k in s:
                if len(sub_sequence*k) > len(longest_subsequence):
                    longest_subsequence = sub_sequence*k
        
        return longest_subsequence

The above code first creates a frequency table of all the characters in the string and then creates a dictionary of all the indices where each character appears. It then generates all possible sub-sequences using a recursive function and checks whether each sub-sequence can be repeated K times or not. Finally, it returns the longest sub-sequence that can be repeated K times.

This solution has a time complexity of O(n^k k log n) and a space complexity of O(n + k), where n is the length of the input string s.

1