2014.js

/** ------------------------------------------------------------------------------
 * 
 * 2014. Longest Subsequence Repeated k Times
 * Topics: Backtracking, Greedy
 * https://leetcode.com/problems/longest-subsequence-repeated-k-times/description/?envType=daily-question&envId=2025-06-27
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var longestSubsequenceRepeatedK = function (s, k) {
  const freq = new Uint16Array(26)
  for (const ch of s) freq[ch.charCodeAt(0) - "a".charCodeAt(0)]++

  const usable = []
  const quota = new Uint16Array(26)

  for (let i = 25; i >= 0; i--) {
    const q = Math.floor(freq[i] / k)
    if (q > 0) {
      quota[i] = q
      usable.push(String.fromCharCode("a".charCodeAt(0) + i)) // reverse lex
    }
  }

  const maxLen = Math.floor(s.length / k)

  const isValid = (seq) => {
    let i = 0,
      count = 0
    for (let j = 0; j < s.length && count < k; j++) {
      if (s[j] === seq[i]) i++
      if (i === seq.length) {
        i = 0
        count++
      }
      // Early exit if not enough characters left to complete matches
      if (s.length - j < seq.length - i + (k - count - 1) * seq.length) return false
    }
    return count === k
  }

  let queue = [""]
  let result = ""

  for (let len = 1; len <= maxLen; len++) {
    const nextQueue = []
    for (const seq of queue) {
      for (const ch of usable) {
        const newSeq = seq + ch

        // Only continue if within char quota
        const counts = new Uint8Array(26)
        let validCount = true
        for (const c of newSeq) {
          const idx = c.charCodeAt(0) - "a".charCodeAt(0)
          counts[idx]++
          if (counts[idx] > quota[idx]) {
            validCount = false
            break
          }
        }
        if (!validCount) continue

        if (isValid(newSeq)) {
          if (newSeq.length > result.length || (newSeq.length === result.length && newSeq > result)) {
            result = newSeq
          }
          nextQueue.push(newSeq)
        }
      }
    }
    queue = nextQueue
  }

  return result
}