# 2014. Longest Subsequence Repeated k Times

• Time: $O(n \cdot P(7, k))$
• Space: $O(P(7, k))$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution { public: string longestSubsequenceRepeatedK(string s, int k) { string ans; vector count(26); vector possibleChars; queue q{{""}}; // Store subseqs, length grows by 1 each time for (const char c : s) ++count[c - 'a']; for (char c = 'a'; c <= 'z'; ++c) if (count[c - 'a'] >= k) possibleChars.push_back(c); while (!q.empty()) { const string currSubseq = q.front(); q.pop(); if (currSubseq.length() * k > s.length()) return ans; for (const char c : possibleChars) { const string& newSubseq = currSubseq + c; if (isSubsequence(newSubseq, s, k)) { q.push(newSubseq); ans = newSubseq; } } } return ans; } private: bool isSubsequence(const string& subseq, string& s, int k) { int i = 0; // subseq's index for (const char c : s) if (c == subseq[i]) if (++i == subseq.length()) { if (--k == 0) return true; i = 0; } return false; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 public class Solution { public String longestSubsequenceRepeatedK(String s, int k) { String ans = ""; int[] count = new int[26]; List possibleChars = new ArrayList<>(); // Store subseqs, length grows by 1 each time Queue q = new ArrayDeque<>(Arrays.asList("")); for (final char c : s.toCharArray()) ++count[c - 'a']; for (char c = 'a'; c <= 'z'; ++c) if (count[c - 'a'] >= k) possibleChars.add(c); while (!q.isEmpty()) { final String currSubseq = q.poll(); if (currSubseq.length() * k > s.length()) return ans; for (final char c : possibleChars) { final String newSubseq = currSubseq + c; if (isSubsequence(newSubseq, s, k)) { q.offer(newSubseq); ans = newSubseq; } } } return ans; } private boolean isSubsequence(final String subseq, final String s, int k) { int i = 0; // subseq's index for (final char c : s.toCharArray()) if (c == subseq.charAt(i)) if (++i == subseq.length()) { if (--k == 0) return true; i = 0; } return false; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution: def longestSubsequenceRepeatedK(self, s: str, k: int) -> str: ans = '' count = [0] * 26 possibleChars = [] q = collections.deque(['']) # Store subseqs, length grows by 1 each time for c in s: count[ord(c) - ord('a')] += 1 for c in string.ascii_lowercase: if count[ord(c) - ord('a')] >= k: possibleChars.append(c) def isSubsequence(subseq: str, s: str, k: int) -> bool: i = 0 # subseq's index for c in s: if c == subseq[i]: i += 1 if i == len(subseq): k -= 1 if k == 0: return True i = 0 return False while q: currSubseq = q.popleft() if len(currSubseq) * k > len(s): return ans for c in possibleChars: newSubseq = currSubseq + c if isSubsequence(newSubseq, s, k): q.append(newSubseq) ans = newSubseq return ans