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 string 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 the string s if seq * k is a subsequence of s, where seq * k represents a string constructed by concatenating seq k times.


	For example, "bba" is repeated 2 times in the string "bababcba", because the string "bbabba", constructed by concatenating "bba" 2 times, is a subsequence of the string "bababcba".


Return the longest subsequence repeated k times in string s. If multiple such subsequences are found, return the lexicographically largest one. If there is no such subsequence, return an empty string.

&nbsp;
Example 1:

Input: s = "letsleetcode", k = 2
Output: "let"
Explanation: There are two longest subsequences repeated 2 times: "let" and "ete".
"let" is the lexicographically largest one.


Example 2:

Input: s = "bb", k = 2
Output: "b"
Explanation: The longest subsequence repeated 2 times is "b".


Example 3:

Input: s = "ab", k = 2
Output: ""
Explanation: There is no subsequence repeated 2 times. Empty string is returned.


&nbsp;
Constraints:


	n == s.length
	2 &lt;= n, k &lt;= 2000
	2 &lt;= n &lt; k * 8
	s consists of lowercase English letters.


class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        n = len(s)
        max_chunk_sz = n // k
        
        d = collections.Counter(s)
        chars = sorted([c for c in d if d[c] >= k], reverse=True)
        if not chars:
            return ''
        
        old_cand = chars
        for m in range(2, max_chunk_sz+1):
            new_cand = []
            for t in self.get_next_level(old_cand, chars):
                if self.find(s, t*k):
                    new_cand.append(t)
            
            if len(new_cand) == 0:
                break
            old_cand = new_cand
        return old_cand[0]
        
    def get_next_level(self, cand, chars):
        for s in cand:
            for ch in chars:
                yield s + ch
        
    def find(self, s, t):
        # find subsequence t in s
        j = 0
        for i in range(len(s)):
            if s[i] == t[j]:
                j += 1
            if j == len(t):
                return True
        return False
class Solution {
    char[] A;
    public String longestSubsequenceRepeatedK(String s, int k) {
        A = s.toCharArray();
        Queue<String> queue = new ArrayDeque<>();
        queue.offer("");
        String ans = "";
        int[] count = new int[26];
        BitSet bit = new BitSet();
        for (char ch : A) if (++count[ch-'a'] >= k){
            bit.set(ch-'a');
        }
        while(!queue.isEmpty()){
            String sb = queue.poll();
            for (int i = bit.nextSetBit(0); i >= 0; i = bit.nextSetBit(i+1)){
                String res = sb+(char)(i+'a');
                if (check(k, res)){
                    ans = res;
                    queue.offer(res);
                }
            }
        }
        return ans;
    }

    private boolean check(int k, String s){
        int cnt = 0;
        for (char ch : A){
            if (s.charAt(cnt%s.length()) == ch && ++cnt >= k * s.length()){
                return true;
            }
        }
        return false;
    }
}
class Solution {
public:
    int Alpha=26;
    bool find(string &s,string &p,int k)
    {
        int j=0;
        int n=s.size();
        int count=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]==p[j])
            {
                j++;
                if(j==p.size())
                {
                    count++;
                    j=0;
                }
                if(count==k)
                {
                    return true;
                }
            }
        }
        return false;
    }
    string longestSubsequenceRepeatedK(string s, int k) 
    {
        queue<string>q;
        q.push("");
        string ans="";
        while(q.size())
        {
            auto temp=q.front();
            q.pop();
            for(int i=0;i<Alpha;i++)
            {
                string curr=temp+char('a'+i);
                if(find(s,curr,k))
                {
                    ans=curr;
                    q.push(curr);
                }
            }
        }
        return ans;
    }
};
// Idea comes from:
// https://leetcode.com/problems/longest-subsequence-repeated-k-times/discuss/1471930/Python-Answer-is-not-so-long-explained

var longestSubsequenceRepeatedK = function(s, k) {
  const freq = {};
  for (const c of s) {
    if (!freq[c]) freq[c] = 0;
    freq[c]++;
  }

  // Find hot string
  let hot = "";
  for (const [c, cnt] of Object.entries(freq)) {
    const repeat = Math.floor(cnt / k);
    hot += c.repeat(repeat);
  }

  // Find all subset and permutation of hot string
  let targets = new Set();
  const subsets = getSubset(hot);
  for (const subset of subsets) {
    const permutations = getPermutation(subset);
    for (const per of permutations) targets.add(per);
  }

  // Sort targets by length and lexico
  targets = [...targets].sort((a, b) => {
    const delta = b.length - a.length;
    if (delta) return delta;
    return b.localeCompare(a);
  });

  // Filter s and check subsequence
  s = [...s].filter(c => hot.includes(c)).join("");
  for (const tar of targets) {
    if (isSubsequence(s, tar.repeat(k))) return tar;
  }

  return "";
};

function getSubset(str) {
  const res = [""];
  for (const c of str) {
    res.push(...res.map((curStr) => curStr + c));
  }
  return [...new Set(res)];
};

function getPermutation(str) {
  let res = [""];
  for (const c of str) {
    const resT = [];
    for (const cur of res) {
      for (let i = 0; i <= cur.length; i++) {
        const curT = cur.substring(0, i) + c + cur.substring(i);
        resT.push(curT);
      }
    }
    res = resT;
  }
  return [...new Set(res)];
};

function isSubsequence(s, t) {
  let i = 0;
  for (let j = 0; j < s.length; j++) {
    if (t[i] === s[j]) {
      i++;
      if (i === t.length) return true;
    }
  }
  return false;
}
Longest Subsequence Repeated k Times