Longest subsequence repeated k times

Hash Table Two Pointers String Backtracking Counting Enumeration

71.3% acceptance

Feb 25, 2026

824

117

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

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn longest_subsequence_repeated_k(s: String, k: i32) -> String {
    // Since n < k*8, max length of answer is 7 (each char must appear at least k times)
    let k = k as usize;
    let s: Vec<u8> = s.bytes().collect();
    
    // Count chars that appear >= k times - only these can be in the answer
    let mut freq = [0usize; 26];
    for &c in &s { freq[(c - b'a') as usize] += 1; }
    let valid: Vec<u8> = (0..26u8)
      .filter(|&i| freq[i as usize] >= k)
      .map(|i| b'a' + i)
      .collect();
    
    // BFS/BFS over candidate subsequences in increasing length
    // Check if seq repeated k times is a subsequence of s
    let is_subseq_k = |seq: &[u8]| -> bool {
      if seq.is_empty() { return true; }
      let mut rep = 0;
      let mut idx = 0;
      let n = s.len();
      let m = seq.len();
      while rep < k {
        let mut j = 0;
        while j < m && idx < n {
          if s[idx] == seq[j] { j += 1; }
          idx += 1;
        }
        if j < m { return false; }
        rep += 1;
      }
      true
    };
    
    // BFS: level = length
    let mut candidates: Vec<Vec<u8>> = vec![vec![]];
    let mut best: Vec<u8> = vec![];
    
    loop {
      let mut next_level: Vec<Vec<u8>> = vec![];
      let mut level_best: Vec<u8> = vec![];
      for cand in &candidates {
        for &c in &valid {
          let mut next = cand.clone();
          next.push(c);
          if is_subseq_k(&next) {
            if next > level_best { level_best = next.clone(); }
            next_level.push(next);
          }
        }
      }
      if next_level.is_empty() { break; }
      best = level_best;
      candidates = next_level;
    }
    
    String::from_utf8(best).unwrap()
  }
}