2014：重复 K 次的最长子序列（2558 分）

力扣第 259 场周赛第 4 题

题目

给你一个长度为 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：

输入：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 由小写英文字母组成

相似问题：

• 0395：至少有 K 个重复字符的最长子串

分析

#1

• 注意到 n<k*8，那么子序列长度最多为 7，因此可以暴力枚举所有可能的子序列
• 假如字符 c 在 s 中有 w 个，那么最多 w//k 个参与子序列
• 遍历字符 c，得到候选集合 A，A 长度最多 7
• 从长到短，从大到小枚举 A 的排列，返回第一个在 s 中重复 k 次的子序列即可
• 枚举排列可以用回溯法，也可以直接调包

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        A = []
        for c,w in Counter(s).items():
            A.extend([c]*(w//k))
        A = sorted(A)[::-1]
        for i in range(len(A),0,-1):
            for B in permutations(A,i):
                it = iter(s)
                if all(c in it for c in B*k):
                    return ''.join(B)
        return ''

2023 ms

#2

• 也可以考虑从短到长枚举排列，假如某个子序列 u 不能重复 k 次，那么以 u 为前缀的子序列都不能
• 因此用 bfs，在子序列 u 后添加 A 中的字符 c，判断 v=u+c 能否重复 k 次，再入队即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        res = ''
        A = sorted(c for c,w in Counter(s).items() if w>=k)
        Q = deque(A)
        while Q:
            u = Q.popleft()
            res = u
            for c in A:
                v = u+c
                it = iter(s)
                if all(a in it for a in v*k):
                    Q.append(v)
        return res

963 ms