# Longest Subsequence Repeated k Times
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-subsequence-repeated-k-times)
Canonical: https://scaleengineer.com/dsa/problems/longest-subsequence-repeated-k-times
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Counting](https://scaleengineer.com/dsa/patterns/counting), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** String
---
## Problem
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 `"**b**a**bab**c**ba**"`.

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_.

**Example 1:**

![example 1](https://assets.glich.co/dsa/longest-subsequence-repeated-k-times/image0.png) 

**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.

**Constraints:**

* `n == s.length`
* `2 <= n, k <= 2000`
* `2 <= n < k * 8`
* `s` consists of lowercase English letters.

# Approaches
## Recursive Backtracking (DFS)
This approach uses a recursive Depth-First Search (DFS) to explore all possible candidate subsequences. It starts with an empty string and recursively tries to append 'hot' characters (those appearing at least `k` times in the input string `s`). For every valid subsequence found, it compares it with the best result found so far and updates it if the new one is better (longer or lexicographically larger).
**Time:** O(M^L * N), where N is the length of `s`, M is the number of 'hot' characters (≤ 7), and L is the max length of the answer (≤ 7). In the worst case, it explores a large number of candidates, and each check takes O(N) time. · **Space:** O(L), where L is the maximum length of the subsequence (at most 7). This space is used by the recursion stack.
**Pros:** Conceptually simple to implement using recursion.; Uses less memory for the call stack compared to the BFS queue in many cases, as it only stores one path at a time.
**Cons:** The search order is not optimal for this problem. It may explore deep, unpromising paths first (e.g., a long but lexicographically small sequence).; To guarantee the lexicographically largest result among the longest subsequences, it must explore all possible valid subsequences and compare them, which is less direct than the BFS approach.
### Explanation
The core idea is to build the candidate subsequence character by character. We first determine the set of possible characters for our subsequence, which are those with a frequency of at least `k` in the string `s`. Then, a backtracking function explores all combinations of these characters up to the maximum possible length (`n/k`).

The backtracking function, say `backtrack(currentString)`, would try appending each 'hot' character to `currentString`. For each new string `nextString`, we check if it's a valid k-repeated subsequence. If it is, we update our overall best answer and then recurse further with `backtrack(nextString)` to see if we can build an even longer valid subsequence. Because we need the lexicographically largest among the longest, we must exhaustively check all possibilities and keep track of the best one seen.

```java
class Solution {
    private String result = "";
    private String s;
    private int k;
    private List<Character> hotChars;

    public String longestSubsequenceRepeatedKTimes(String s, int k) {
        this.s = s;
        this.k = k;

        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        this.hotChars = new ArrayList<>();
        for (int i = 25; i >= 0; i--) { // 'z' to 'a' for lexicographical preference
            if (freq[i] >= k) {
                hotChars.add((char) ('a' + i));
            }
        }

        backtrack("");
        return result;
    }

    private void backtrack(String current) {
        if (current.length() > s.length() / k) {
            return;
        }

        for (char c : hotChars) {
            String next = current + c;
            if (isKSubsequence(s, k, next)) {
                if (next.length() > result.length()) {
                    result = next;
                } else if (next.length() == result.length() && next.compareTo(result) > 0) {
                    result = next;
                }
                backtrack(next);
            }
        }
    }

    private boolean isKSubsequence(String s, int k, String sub) {
        if (sub.length() == 0) return true;
        int subPtr = 0;
        int repeatCount = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == sub.charAt(subPtr)) {
                subPtr++;
                if (subPtr == sub.length()) {
                    repeatCount++;
                    subPtr = 0;
                    if (repeatCount == k) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
```
### Algorithm
*   **Filter Hot Characters**: Identify characters in `s` that appear at least `k` times. These are the only characters that can form the result.
*   **Recursive Function**: Define a recursive function, e.g., `find(current_candidate)`, which attempts to extend the `current_candidate`.
*   **Base Case**: The recursion stops if `current_candidate`'s length exceeds the maximum possible length, which is `n / k`.
*   **Recursive Step**: The function iterates through the hot characters. For each character `c`, it forms a new candidate `next = current_candidate + c`.
*   **Validation**: It checks if `next` is a valid k-repeated subsequence using a helper function `isKSubsequence`. This helper verifies if `next` repeated `k` times is a subsequence of `s`.
*   **Update Global Result**: If `next` is valid, it's compared with a global best-answer variable. The global answer is updated if `next` is longer, or of the same length but lexicographically larger.
*   **Recurse**: If `next` is a valid candidate, a recursive call `find(next)` is made to explore longer subsequences.
*   **Initiation**: The process starts with an initial call `find("")`.

## Breadth-First Search on Candidate Subsequences
This approach systematically builds candidate subsequences level by level using Breadth-First Search (BFS). It starts with an empty string and iteratively adds characters to generate longer candidates. The search is highly efficient due to the problem's constraints: the answer's length is very small (at most 7), and its characters must appear at least `k` times in the original string. By exploring candidates by length and in reverse lexicographical order, this method naturally and efficiently arrives at the optimal solution.
**Time:** O(N + V_total * M * N), where N is `s.length()`, M is number of hot characters, and `V_total` is the total number of valid subsequences found. The search space is small enough (`M, L <= 7`) that this is feasible. Each check `isKSubsequence` takes O(N). · **Space:** O(V), where V is the maximum number of valid subsequences at any given length. In the worst case, this can be O(M^L), where M is the number of hot characters (≤ 7) and L is the length (≤ 7).
**Pros:** The level-by-level nature of BFS guarantees that we find the longest possible subsequence.; By iterating characters in reverse lexicographical order ('z' to 'a') at each level, it ensures the resulting subsequence is the lexicographically largest among all longest ones.; Efficiently prunes the search space by only attempting to extend subsequences that are already verified as valid.
**Cons:** Can potentially use more memory than a DFS approach because the queue might need to store all valid subsequences of a certain length simultaneously.
### Explanation
The key insight is that any valid subsequence of length `L` must be an extension of a valid subsequence of length `L-1`. This property makes BFS a perfect fit.

1.  **Preprocessing**: We first identify the 'hot characters' that can possibly be in our answer. A character `c` can be in the subsequence `seq` only if its frequency in `s` is at least `k`. We gather these characters.

2.  **BFS Setup**: We initialize a queue with an empty string. This queue will hold all valid k-repeated subsequences found so far. We also have a variable `ans` to keep track of the best valid subsequence. The BFS proceeds level by level, where each level corresponds to a specific length of the subsequence.

3.  **Search**: We dequeue a valid subsequence `curr`. We then try to extend it by one character by appending each 'hot character' `c`. To ensure we find the lexicographically largest result, we iterate through the hot characters from 'z' down to 'a'. For each new candidate `next = curr + c`, we check if it's a valid k-repeated subsequence. The check is done by a helper function that greedily verifies if `next * k` is a subsequence of `s` in `O(N)` time.

4.  **Finding the Answer**: If `next` is valid, we update `ans = next` and add `next` to the queue. Because BFS explores all candidates of length `L` before moving to `L+1`, and for each length, we try characters in `z...a` order, the last update to `ans` will be the final answer. The search space is naturally pruned because we only extend subsequences that are already confirmed to be valid.

```java
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public String longestSubsequenceRepeatedKTimes(String s, int k) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        List<Character> hotChars = new ArrayList<>();
        for (int i = 25; i >= 0; i--) { // Iterate 'z' to 'a' for lexicographical order
            if (freq[i] >= k) {
                hotChars.add((char) ('a' + i));
            }
        }

        String result = "";
        Queue<String> queue = new LinkedList<>();
        queue.offer("");

        while (!queue.isEmpty()) {
            String current = queue.poll();

            if (current.length() >= s.length() / k) {
                continue;
            }

            for (char c : hotChars) {
                String next = current + c;
                if (isKSubsequence(s, k, next)) {
                    result = next;
                    queue.offer(next);
                }
            }
        }
        return result;
    }

    private boolean isKSubsequence(String s, int k, String sub) {
        if (sub.length() == 0) {
            return true;
        }
        int subPtr = 0;
        int repeatCount = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == sub.charAt(subPtr)) {
                subPtr++;
                if (subPtr == sub.length()) {
                    repeatCount++;
                    subPtr = 0;
                    if (repeatCount == k) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
```
### Algorithm
*   **Filter Hot Characters**: First, count character frequencies in `s`. Collect all characters that appear at least `k` times into a list of 'hot characters'. Sort this list in descending lexicographical order (from 'z' to 'a').
*   **Initialize BFS**: Create a queue and add an empty string `""` to it. This represents a valid subsequence of length 0. Initialize a string `result = ""` to store the answer.
*   **BFS Traversal**: While the queue is not empty, dequeue a candidate string `current`.
*   **Extend and Check**: For each character `c` in the sorted list of hot characters:
    *   Form a new candidate `next = current + c`.
    *   Check if `next` is a valid k-repeated subsequence using a helper function `isKSubsequence(s, k, next)`.
*   **Update and Enqueue**: If `next` is valid:
    *   Update `result = next`. Because we are building level-by-level (longest) and trying characters from 'z' to 'a' (lexicographically largest), this `next` is guaranteed to be the best candidate found so far.
    *   Enqueue `next` to be used for building even longer candidates.
*   **Return Result**: After the BFS completes, `result` will hold the longest and lexicographically largest valid subsequence.

# Solutions
### Java

```java
class Solution {
private
  char[] s;
public
  String longestSubsequenceRepeatedK(String s, int k) {
    this.s = s.toCharArray();
    int[] cnt = new int[26];
    for (char c : this.s) {
      cnt[c - 'a']++;
    }
    List<Character> cs = new ArrayList<>();
    for (char c = 'a'; c <= 'z'; ++c) {
      if (cnt[c - 'a'] >= k) {
        cs.add(c);
      }
    }
    Deque<String> q = new ArrayDeque<>();
    q.offer("");
    String ans = "";
    while (!q.isEmpty()) {
      String cur = q.poll();
      for (char c : cs) {
        String nxt = cur + c;
        if (check(nxt, k)) {
          ans = nxt;
          q.offer(nxt);
        }
      }
    }
    return ans;
  }
private
  boolean check(String t, int k) {
    int i = 0;
    for (char c : s) {
      if (c == t.charAt(i)) {
        i++;
        if (i == t.length()) {
          if (--k == 0) {
            return true;
          }
          i = 0;
        }
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  string longestSubsequenceRepeatedK(string s, int k) {
    auto check = [&](const string &t, int k) -> bool {
      int i = 0;
      for (char c : s) {
        if (c == t[i]) {
          i++;
          if (i == t.size()) {
            if (--k == 0) {
              return true;
            }
            i = 0;
          }
        }
      }
      return false;
    };
    int cnt[26] = {};
    for (char c : s) {
      cnt[c - 'a']++;
    }
    vector<char> cs;
    for (char c = 'a'; c <= 'z'; ++c) {
      if (cnt[c - 'a'] >= k) {
        cs.push_back(c);
      }
    }
    queue<string> q;
    q.push("");
    string ans;
    while (!q.empty()) {
      string cur = q.front();
      q.pop();
      for (char c : cs) {
        string nxt = cur + c;
        if (check(nxt, k)) {
          ans = nxt;
          q.push(nxt);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str: def check(t: str, k: int) -> bool: i = 0 for c in s: if c == t[i]: i += 1 if i == len(t): k -= 1 if k == 0: return True i = 0 return False cnt = Counter(s) cs = [c for c in ascii_lowercase if cnt[c] >= k] q = deque([""]) ans = "" while q: cur = q . popleft() for c in cs: nxt = cur + c if check(nxt, k): ans = nxt q . append(nxt) return ans

```