重复 K 次的最长子序列

标签: 贪心字符串回溯计数枚举

难度: Hard

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

子序列 是由其他字符串删除某些（或不删除）字符派生而来的一个字符串。

如果 seq * k 是 s 的一个子序列，其中 seq * k 表示一个由 seq 串联 k 次构造的字符串，那么就称 seq 是字符串 s 中一个 重复 k 次 的子序列。

举个例子，"bba" 是字符串 "bababcba" 中的一个重复 2 次的子序列，因为字符串 "bbabba" 是由 "bba" 串联 2 次构造的，而 "bbabba" 是字符串 "bababcba" 的一个子序列。

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

示例 1：

example 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 < k * 8
s 由小写英文字母组成

Submission

运行时间: 1392 ms

内存: 18.2 MB

class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        lst = [ord(w) - ord("a") for w in s]
        n = len(s)
        nxt = [-1] * 26 * n
        post = dict()
        for i in range(n - 1, -1, -1):
            post[lst[i]] = i
            for j in post:
                nxt[i * 26 + j] = post[j]

        cnt = Counter(lst)
        hot = []
        for w in sorted(cnt, reverse=True):
            hot.extend([w] * (cnt[w] // k))

        pre = set()
        for m in range(min(len(hot), 7), 0, -1):
            for item in permutations(hot, m):
                if item in pre:
                    continue
                pre.add(item)
                i = j = 0
                while j < k * m and i < n:
                    i = nxt[i * 26 + item[j % m]]
                    if i == -1:
                        break
                    i += 1
                    j += 1
                if j == k * m:
                    word = "".join([chr(x + ord("a")) for x in item])
                    return word
        return ""

Explain

此题解的思路首先是将字符串s转换为字符的整数表示，便于后续操作。然后构建一个next数组，用于快速定位字符在字符串中的下一个出现位置，这是通过逆序遍历字符串s并记录每个字符最后出现位置来实现的。接着，利用字符频数统计，确定哪些字符的出现次数至少是k的倍数，这些字符可能构成最终答案的一部分。题解尝试所有可能的组合（长度从1到7），使用排列尝试构建子序列，检查是否能在字符串s中重复出现k次。这一步使用next数组进行快速验证。最后，返回字典序最大的有效子序列。

时间复杂度: O(n + 7^7 * km)

空间复杂度: O(n + 7^7)

class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        lst = [ord(w) - ord('a') for w in s]  # 将字符转换为0-25的整数表示
        n = len(s)
        nxt = [-1] * 26 * n  # 初始化next数组
        post = dict()  # 用于记录字符的最后出现位置
        for i in range(n - 1, -1, -1):
            post[lst[i]] = i
            for j in post:
                nxt[i * 26 + j] = post[j]  # 更新next数组

        cnt = Counter(lst)
        hot = []
        for w in sorted(cnt, reverse=True):
            hot.extend([w] * (cnt[w] // k))  # 选取可能构成答案的字符集合

        pre = set()
        for m in range(min(len(hot), 7), 0, -1):
            for item in permutations(hot, m):
                if item in pre:
                    continue
                pre.add(item)
                i = j = 0
                while j < k * m and i < n:
                    i = nxt[i * 26 + item[j % m]]
                    if i == -1:
                        break
                    i += 1
                    j += 1
                if j == k * m:
                    word = ''.join([chr(x + ord('a')) for x in item])
                    return word
        return ''

Explore

在构建next数组时选择逆序遍历字符串s是为了方便地记录每个字符最近一次出现的位置。逆序遍历可以确保在遍历到某个字符时，直接使用已记录的信息更新next数组。如果使用正序遍历，则需要额外记录每个字符接下来的出现位置，这会使得逻辑更为复杂并可能增加错误发生的概率。

字符的整数表示（从0至25）通过简化字符处理帮助优化算法，使得字符可以直接作为数组索引使用，从而提高访问效率和减少内存使用。其他方法，如直接使用字符作为字典的键，虽然可行，但通常会比直接使用整数索引慢，并且在内存使用上也不如数组索引高效。

使用next数组进行快速验证的逻辑是通过next数组快速定位字符串中字符的下一个出现位置。具体步骤是：通过next数组，从当前位置开始查找子序列中的下一个字符。如果找到，继续向后查找；如果找不到，表示子序列不能在字符串中重复出现k次。这种方法大大减少了查找每个可能的子序列出现位置的时间复杂度，从而提高了整体算法的效率。

子序列长度限制在7以内主要是出于性能考虑。考虑到排列的数量随着长度增加而急剧增加，长度大于7的排列会导致计算量过大，从而影响算法效率。这并不意味着超过7个字符的子序列不可能存在，但在实际应用中，限制长度可以在接受的时间内得到结果。