Hard

题目描述

给你一个长度为 n 的字符串 s 和一个整数 k。请你找出字符串 s 中重复 k 次的最长子序列。

子序列 是一个可以从另一个字符串中删除某些或不删除字符而不改变剩余字符顺序的字符串。

如果 seq * k 是 s 的一个子序列，那么子序列 seq 在字符串 s 中重复 k 次，其中 seq * k 表示将 seq 连接 k 次构造的字符串。

  • 例如，"bba" 在字符串 "bababcba" 中重复 2 次，因为字符串 "bbabba"（由 "bba" 连接 2 次构成）是字符串 "bababcba" 的一个子序列。

返回字符串 s 中重复 k 次的最长子序列。如果存在多个这样的子序列，返回字典序最大的那个。如果不存在这样的子序列，返回空字符串。

示例 1：

输入：s = "letsleetcode", k = 2
输出："let"
解释：有两个长度最长的子序列重复 2 次："let" 和 "ete"。
"let" 是字典序最大的一个。

示例 2：

输入：s = "bb", k = 2
输出："b"
解释：重复 2 次的最长子序列是 "b"。

示例 3：

输入：s = "ab", k = 2
输出：""
解释：不存在重复 2 次的子序列。返回空字符串。

约束条件：

  • n == s.length
  • 2 <= k <= 2000
  • 2 <= n < min(2001, k * 8)
  • s 由小写英文字母组成

解题思路

这道题的核心思路是通过回溯枚举所有可能的候选子序列，然后验证是否满足重复 k 次的条件。

关键观察：

  1. 最长子序列的长度不会超过 n/k，因为每个字符至少需要出现 k 次才能构成重复 k 次的子序列
  2. 只有出现次数 ≥ k 的字符才可能被包含在答案中，且每个字符最多使用 count[c]/k 次
  3. 为了找到字典序最大的答案，我们按字典序逆序（从 ‘z’ 到 ‘a’）枚举候选字符

算法步骤：

  1. 统计每个字符的出现次数，筛选出可用字符及其最大使用次数
  2. 使用回溯法按字典序逆序枚举所有可能的子序列
  3. 对每个候选子序列，验证其重复 k 次后是否为原字符串的子序列
  4. 返回最长且字典序最大的有效子序列

验证子序列时，我们需要检查 candidate * k 是否为 s 的子序列，这可以通过双指针技术高效完成。

代码实现

class Solution {
public:
    string longestSubsequenceRepeatedK(string s, int k) {
        // 统计字符频次
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }
        
        // 找到可用字符
        string candidates;
        for (int i = 0; i < 26; i++) {
            if (count[i] >= k) {
                candidates += char('a' + i);
            }
        }
        
        string result = "";
        
        function<void(string)> backtrack = [&](string current) {
            if (current.length() > result.length() || 
                (current.length() == result.length() && current > result)) {
                result = current;
            }
            
            // 按字典序逆序尝试添加字符
            for (int i = candidates.length() - 1; i >= 0; i--) {
                char c = candidates[i];
                string next = current + c;
                
                // 检查使用次数是否超限
                int usage = 0;
                for (char ch : next) {
                    if (ch == c) usage++;
                }
                if (usage > count[c - 'a'] / k) continue;
                
                // 验证是否为有效子序列
                if (isValidSubsequence(s, next, k)) {
                    backtrack(next);
                }
            }
        };
        
        backtrack("");
        return result;
    }
    
private:
    bool isValidSubsequence(const string& s, const string& pattern, int k) {
        string target = "";
        for (int i = 0; i < k; i++) {
            target += pattern;
        }
        
        int i = 0, j = 0;
        while (i < s.length() && j < target.length()) {
            if (s[i] == target[j]) {
                j++;
            }
            i++;
        }
        return j == target.length();
    }
};

class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        from collections import Counter
        
        # 统计字符频次
        count = Counter(s)
        
        # 找到可用字符
        candidates = [c for c in count if count[c] >= k]
        
        def is_valid_subsequence(s, pattern, k):
            target = pattern * k
            i = j = 0
            while i < len(s) and j < len(target):
                if s[i] == target[j]:
                    j += 1
                i += 1
            return j == len(target)
        
        result = ""
        
        def backtrack(current):
            nonlocal result
            
            if len(current) > len(result) or (len(current) == len(result) and current > result):
                result = current
            
            # 按字典序逆序尝试添加字符
            for c in sorted(candidates, reverse=True):
                next_seq = current + c
                
                # 检查使用次数是否超限
                if next_seq.count(c) > count[c] // k:
                    continue
                
                # 验证是否为有效子序列
                if is_valid_subsequence(s, next_seq, k):
                    backtrack(next_seq)
        
        backtrack("")
        return result

public class Solution {
    public string LongestSubsequenceRepeatedK(string s, int k) {
        // 统计字符频次
        int[] count = new int[26];
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        // 找到可用字符
        List<char> candidates = new List<char>();
        for (int i = 0; i < 26; i++) {
            if (count[i] >= k) {
                candidates.Add((char)('a' + i));
            }
        }
        
        string result = "";
        
        void Backtrack(string current) {
            if (current.Length > result.Length || 
                (current.Length == result.Length && string.Compare(current, result) > 0)) {
                result = current;
            }
            
            // 按字典序逆序尝试添加字符
            for (int i = candidates.Count - 1; i >= 0; i--) {
                char c = candidates[i];
                string next = current + c;
                
                // 检查使用次数是否超限
                int usage = 0;
                foreach (char ch in next) {
                    if (ch == c) usage++;
                }
                if (usage > count[c - 'a'] / k) continue;
                
                // 验证是否为有效子序列
                if (IsValidSubsequence(s, next, k)) {
                    Backtrack(next);
                }
            }
        }
        
        Backtrack("");
        return result;
    }
    
    private bool IsValidSubsequence(string s, string pattern, int k) {
        string target = "";
        for (int i = 0; i < k; i++) {
            target += pattern;
        }
        
        int i = 0, j = 0;
        while (i < s.Length && j < target.Length) {
            if (s[i] == target[j]) {
                j++;
            }
            i++;
        }
        return j == target.Length;
    }
}

var longestSubsequenceRepeatedK = function(s, k) {
    function canFormSubsequence(s, target, k) {
        let count = 0;
        let j = 0;
        
        for (let i = 0; i < s.length && count < k; i++) {
            if (s[i] === target[j]) {
                j++;
                if (j === target.length) {
                    count++;
                    j = 0;
                }
            }
        }
        
        return count >= k;
    }
    
    let queue = [''];
    let result = '';
    
    while (queue.length > 0) {
        let current = queue.shift();
        
        if (current.length > result.length || 
            (current.length === result.length && current > result)) {
            result = current;
        }
        
        for (let c = 'a'.charCodeAt(0); c <= 'z'.charCodeAt(0); c++) {
            let char = String.fromCharCode(c);
            let next = current + char;
            
            if (canFormSubsequence(s, next, k)) {
                queue.push(next);
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(C^L × n × k × L)，其中 C 是可用字符数，L 是最长子序列长度，n 是字符串长度
空间复杂度O(L + k × L) = O(k × L)，递归栈空间和验证子序列时的临时字符串空间

相关题目