HardRating 2558

2014. Longest Subsequence Repeated k Times

hash-tabletwo-pointersstringbacktrackingcountingenumeration

解題說明

Longest Subsequence Repeated k Times

題目描述：給定字串 s 和整數 k，找出最長的子序列 seq，使得 seq 重複 k 次後仍是 s 的子序列。若有多個等長答案，回傳字典序最大的。

解題思路：關鍵觀察是 seq 的長度最多為 n/k（因為重複 k 次要嵌入 s 中）。首先統計每個字元出現次數，只有出現至少 k 次的字元才可能出現在 seq 中。n/k 最多為 7（n <= 2000, k >= 2），所以候選序列很短。用 BFS 按長度遞增枚舉所有候選序列（字典序降序），對每個候選檢查其重複 k 次是否為 s 的子序列。找到的第一個最長且字典序最大的即為答案。

C++ 解法

複雜度分析

時間複雜度：O(C^(n/k) × n) — C 為合格字元數，n/k 為最大序列長度，每次檢查需要 O(n)。由於 n/k <= 7 且 C 通常很小，實際上非常快。

空間複雜度：O(C^(n/k)) — BFS 佇列中的候選序列數量。

虛擬碼

1. Count frequency of each character in s
2. Collect characters appearing >= k times (descending order for lex)
3. check(seq): verify seq repeated k times is a subsequence of s using two pointers
4. BFS starting from empty string:
   a. For each candidate, try appending each valid character
   b. If extended sequence passes check, add to queue
   c. Track the longest (and lexicographically largest) valid sequence
5. Return best sequence found

其他解法

DFS + 剪枝：用 DFS 從長到短嘗試序列，找到第一個合法序列即為答案（長度優先）。加上字典序降序的枚舉順序和提前終止，效率可能更高。

DP 預處理 next 陣列：預計算 next[i][c] 表示 s 中位置 i 之後第一次出現字元 c 的位置。將 check 函式從 O(n) 加速到 O(|seq| × k)，減少重複掃描。

延伸思考

若不要求字典序最大，而是要求所有最長子序列的數量，如何計算？
若 k 為 1（即找最長的本身為 s 子序列的字串），問題退化為什麼？
若 s 中的字元有權重，要最大化重複子序列的權重和，如何修改？

Longest Subsequence Repeated k Times — CaffeCode