Longest Subsequence Repeated k Times

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

Examples

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.

Constraints

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

Solution

Method 1 – BFS

Intuition

To solve this problem, we need to find the longest subsequence that, when repeated k times, remains a subsequence of the original string s, and among all such subsequences, select the lexicographically largest one. Since only characters that appear at least k times in s can contribute to such a subsequence, we can filter out less frequent characters immediately.

Approach

1. Count the frequency of each character in s and retain only those that appear at least k times.
2. The maximum possible length of a valid subsequence is limited by the constraint n < 8k, so the answer's length cannot exceed 7.
3. Generate all possible combinations and permutations of the filtered characters up to the maximum allowed length.
4. Use a queue (BFS) to build candidate subsequences, always extending the current string by appending valid characters in reverse lexicographical order to prioritize larger answers.
5. For each candidate, check if its k-fold concatenation is a subsequence of s. The first valid candidate found with the maximum length and lexicographical order is the answer.

Code

C++

class Solution {
public:
  string longestSubsequenceRepeatedK(string s, int k) {
    vector<int> freq(26, 0);
    for (char ch : s) freq[ch - 'a']++;
    vector<char> candidate;
    for (int i = 25; i >= 0; --i) {
      if (freq[i] >= k) candidate.push_back('a' + i);
    }
    queue<string> q;
    for (char ch : candidate) q.push(string(1, ch));
    string ans;
    while (!q.empty()) {
      string curr = q.front(); q.pop();
      if (curr.length() > ans.length() || (curr.length() == ans.length() && curr > ans)) {
        ans = curr;
      }
      for (char ch : candidate) {
        string next = curr + ch;
        if (isKRepeatedSubsequence(s, next, k)) {
          q.push(next);
        }
      }
    }
    return ans;
  }

  bool isKRepeatedSubsequence(const string& s, const string& t, int k) {
    int pos = 0, matched = 0, m = t.size();
    for (char ch : s) {
      if (ch == t[pos]) {
        pos++;
        if (pos == m) {
          pos = 0;
          matched++;
          if (matched == k) return true;
        }
      }
    }
    return false;
  }
};

Go

func longestSubsequenceRepeatedK(s string, k int) string {
  freq := make([]int, 26)
  for _, ch := range s {
    freq[ch-'a']++
  }
  candidate := []byte{}
  for i := 25; i >= 0; i-- {
    if freq[i] >= k {
      candidate = append(candidate, byte('a'+i))
    }
  }
  q := []string{}
  for _, ch := range candidate {
    q = append(q, string(ch))
  }
  ans := ""
  for len(q) > 0 {
    curr := q[0]
    q = q[1:]
    if len(curr) > len(ans) || (len(curr) == len(ans) && curr > ans) {
      ans = curr
    }
    for _, ch := range candidate {
      next := curr + string(ch)
      if isKRepeatedSubsequence(s, next, k) {
        q = append(q, next)
      }
    }
  }
  return ans
}

func isKRepeatedSubsequence(s, t string, k int) bool {
  pos, matched, m := 0, 0, len(t)
  for i := 0; i < len(s); i++ {
    if s[i] == t[pos] {
      pos++
      if pos == m {
        pos = 0
        matched++
        if matched == k {
          return true
        }
      }
    }
  }
  return false
}

Java

class Solution {
  public String longestSubsequenceRepeatedK(String s, int k) {
    int[] freq = new int[26];
    for (char ch : s.toCharArray()) {
      freq[ch - 'a']++;
    }
    List<Character> candidate = new ArrayList<>();
    for (int i = 25; i >= 0; i--) {
      if (freq[i] >= k) {
        candidate.add((char) ('a' + i));
      }
    }

    Queue<String> q = new LinkedList<>();
    for (char ch : candidate) {
      q.add(String.valueOf(ch));
    }
    String ans = "";
    while (!q.isEmpty()) {
      String curr = q.poll();
      if (curr.length() > ans.length() || (curr.length() == ans.length() && curr.compareTo(ans) > 0)) {
        ans = curr;
      }
      // Try to extend the current string with each candidate character
      for (char ch : candidate) {
        String next = curr + ch;
        if (isKRepeatedSubsequence(s, next, k)) {
          q.add(next);
        }
      }
    }
    return ans;
  }

  private boolean isKRepeatedSubsequence(String s, String t, int k) {
    int pos = 0, matched = 0;
    int m = t.length();
    for (char ch : s.toCharArray()) {
      if (ch == t.charAt(pos)) {
        pos++;
        if (pos == m) {
          pos = 0;
          matched++;
          if (matched == k) {
            return true;
          }
        }
      }
    }
    return false;
  }
}

Kotlin

class Solution {
  fun longestSubsequenceRepeatedK(s: String, k: Int): String {
    val freq = IntArray(26)
    for (ch in s) freq[ch - 'a']++
    val candidate = mutableListOf<Char>()
    for (i in 25 downTo 0) {
      if (freq[i] >= k) candidate.add(('a' + i))
    }
    val q: ArrayDeque<String> = ArrayDeque()
    for (ch in candidate) q.add(ch.toString())
    var ans = ""
    while (q.isNotEmpty()) {
      val curr = q.removeFirst()
      if (curr.length > ans.length || (curr.length == ans.length && curr > ans)) {
        ans = curr
      }
      for (ch in candidate) {
        val next = curr + ch
        if (isKRepeatedSubsequence(s, next, k)) {
          q.add(next)
        }
      }
    }
    return ans
  }

  private fun isKRepeatedSubsequence(s: String, t: String, k: Int): Boolean {
    var pos = 0
    var matched = 0
    val m = t.length
    for (ch in s) {
      if (ch == t[pos]) {
        pos++
        if (pos == m) {
          pos = 0
          matched++
          if (matched == k) return true
        }
      }
    }
    return false
  }
}

Python

from collections import deque, Counter

class Solution:
  def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
    freq = Counter(s)
    candidate = [c for c in reversed('abcdefghijklmnopqrstuvwxyz') if freq[c] >= k]
    q = deque([c for c in candidate])
    ans = ""
    while q:
      curr = q.popleft()
      if len(curr) > len(ans) or (len(curr) == len(ans) and curr > ans):
        ans = curr
      for ch in candidate:
        next_str = curr + ch
        if self.isKRepeatedSubsequence(s, next_str, k):
          q.append(next_str)
    return ans

  def isKRepeatedSubsequence(self, s: str, t: str, k: int) -> bool:
    pos = matched = 0
    m = len(t)
    for ch in s:
      if ch == t[pos]:
        pos += 1
        if pos == m:
          pos = 0
          matched += 1
          if matched == k:
            return True
    return False

Rust

use std::collections::{VecDeque, HashMap};

impl Solution {
  pub fn longest_subsequence_repeated_k(s: String, k: i32) -> String {
    let mut freq = [0; 26];
    for b in s.bytes() {
      freq[(b - b'a') as usize] += 1;
    }
    let mut candidate = Vec::new();
    for i in (0..26).rev() {
      if freq[i] >= k {
        candidate.push((b'a' + i as u8) as char);
      }
    }
    let mut q: VecDeque<String> = candidate.iter().map(|&c| c.to_string()).collect();
    let mut ans = String::new();
    while let Some(curr) = q.pop_front() {
      if curr.len() > ans.len() || (curr.len() == ans.len() && curr > ans) {
        ans = curr.clone();
      }
      for &ch in &candidate {
        let mut next = curr.clone();
        next.push(ch);
        if Self::is_k_repeated_subsequence(&s, &next, k) {
          q.push_back(next);
        }
      }
    }
    ans
  }

  fn is_k_repeated_subsequence(s: &str, t: &str, k: i32) -> bool {
    let (mut pos, mut matched) = (0, 0);
    let m = t.len();
    let t_bytes = t.as_bytes();
    for &b in s.as_bytes() {
      if b == t_bytes[pos] {
        pos += 1;
        if pos == m {
          pos = 0;
          matched += 1;
          if matched == k {
            return true;
          }
        }
      }
    }
    false
  }
}

Complexity

• ⏰ Time complexity: O(n ⋅ m!), where n is the length of the string and m is the maximum possible length of the answer (bounded by the number of characters in s that appear at least k times). For each candidate subsequence (at most m!), checking if it is repeated k times as a subsequence takes O(n) time.
• 🧺 Space complexity: O(m!), since the queue and candidate set can hold up to m! subsequences at any time.