Longest Subsequence Repeated k Times

hard backtracking bfs subsequence greedy

Problem

Given a string s of length n and an integer k, find the longest subsequence seq such that seq concatenated k times (seq * k) is still a subsequence of s. If several are tied for longest, return the lexicographically largest. If none exists, return the empty string.

Inputs = "letsleetcode", k = 2

Output"let"

Both "let" and "ete" repeat twice; "let" is lexicographically larger.

Inputs = "bbabba", k = 2

Output"bba"

"bba" * 2 = "bbabba", which is exactly s, so it is a subsequence.

s (lowercase letters)

k (integer ≥ 2)

def longest_subseq_repeated_k(s, k):
    from collections import Counter
    freq = Counter(s)
    chars = sorted(c for c in freq if freq[c] >= k)
    def is_k_subseq(seq):
        target, j = seq * k, 0
        for ch in s:
            if j < len(target) and ch == target[j]:
                j += 1
        return j == len(target)
    ans = ""
    queue = [""]
    while queue:
        cur = queue.pop(0)
        for c in chars:
            nxt = cur + c
            if is_k_subseq(nxt):
                if len(nxt) > len(ans) or (len(nxt) == len(ans) and nxt > ans):
                    ans = nxt
                queue.append(nxt)
    return ans

function longestSubseqRepeatedK(s, k) {
  const freq = {};
  for (const ch of s) freq[ch] = (freq[ch] || 0) + 1;
  const chars = Object.keys(freq).filter(c => freq[c] >= k).sort();
  const isKSubseq = (seq) => {
    const target = seq.repeat(k);
    let j = 0;
    for (const ch of s)
      if (j < target.length && ch === target[j]) j++;
    return j === target.length;
  };
  let ans = "";
  const queue = [""];
  while (queue.length) {
    const cur = queue.shift();
    for (const c of chars) {
      const nxt = cur + c;
      if (isKSubseq(nxt)) {
        if (nxt.length > ans.length ||
            (nxt.length === ans.length && nxt > ans)) ans = nxt;
        queue.push(nxt);
      }
    }
  }
  return ans;
}

String longestSubseqRepeatedK(String s, int k) {
    int[] freq = new int[26];
    for (char ch : s.toCharArray()) freq[ch - 'a']++;
    StringBuilder chars = new StringBuilder();
    for (int c = 0; c < 26; c++)
        if (freq[c] >= k) chars.append((char) ('a' + c));
    String ans = "";
    Queue<String> queue = new LinkedList<>();
    queue.add("");
    while (!queue.isEmpty()) {
        String cur = queue.poll();
        for (int i = 0; i < chars.length(); i++) {
            String nxt = cur + chars.charAt(i);
            if (isKSubseq(s, nxt, k)) {
                if (nxt.length() > ans.length() ||
                    (nxt.length() == ans.length() && nxt.compareTo(ans) > 0)) ans = nxt;
                queue.add(nxt);
            }
        }
    }
    return ans;
}
boolean isKSubseq(String s, String seq, int k) {
    StringBuilder t = new StringBuilder();
    for (int r = 0; r < k; r++) t.append(seq);
    int j = 0;
    for (char ch : s.toCharArray())
        if (j < t.length() && ch == t.charAt(j)) j++;
    return j == t.length();
}

bool isKSubseq(const string& s, const string& seq, int k) {
    string t;
    for (int r = 0; r < k; r++) t += seq;
    int j = 0;
    for (char ch : s)
        if (j < (int) t.size() && ch == t[j]) j++;
    return j == (int) t.size();
}
string longestSubseqRepeatedK(string s, int k) {
    int freq[26] = {0};
    for (char ch : s) freq[ch - 'a']++;
    string chars;
    for (int c = 0; c < 26; c++)
        if (freq[c] >= k) chars += (char) ('a' + c);
    string ans = "";
    queue<string> q;
    q.push("");
    while (!q.empty()) {
        string cur = q.front(); q.pop();
        for (char c : chars) {
            string nxt = cur + c;
            if (isKSubseq(s, nxt, k)) {
                if (nxt.size() > ans.size() ||
                    (nxt.size() == ans.size() && nxt > ans)) ans = nxt;
                q.push(nxt);
            }
        }
    }
    return ans;
}

Explanation

Because seq * k must fit inside s, every character of seq is used k times, so a useful character must appear at least k times in s. The constraints also force the answer to be short: since n < k · 8, the answer length is at most n / k < 8. That tiny ceiling is what makes a search over candidate strings affordable.

We grow candidate subsequences with a breadth-first search. The queue starts with the empty string. To expand a candidate cur, we append each eligible character (those with frequency ≥ k) and test whether the new string nxt is still a valid answer.

The test is_k_subseq(seq) builds target = seq * k and runs a single left-to-right greedy scan over s, advancing a pointer j each time the current target character is matched. If j reaches the end of target, then seq * k is a subsequence of s.

Whenever a candidate passes the test we record it if it beats the current best (longer wins; on a tie, the lexicographically larger string wins) and push it back on the queue so it can be extended further. Iterating the eligible characters in sorted order, combined with BFS by length, lets the best candidate surface naturally.

When the queue empties, no candidate can be extended any further, and ans holds the longest — and on ties, lexicographically largest — subsequence repeatable k times. If nothing ever passed the test, ans stays the empty string.

Time: O(C · L · n) Space: O(C · L)