2014-重复 K 次的最长子序列

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 11:11:41 2023-09-13 11:11:41 Updated    

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

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

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

  • 举个例子，"bba" 是字符串 "bababcba" 中的一个重复 2 次的子序列，因为字符串 "bbabba" 是由 "bba" 串联 2 次构造的，而 "bbabba" 是字符串 " _ **b**_ a _ **bab**_ c _ **ba**_ " 的一个子序列。

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

示例 1：

![example 1](https://assets.leetcode.com/uploads/2021/08/30/longest-
subsequence-repeat-k-times.png)

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

如果一个字母频率为freq，那么其可能参与组成的子串最多为freq//k个，因此我们只需要统计s中各个字母出现的频率，进行倒序排列便于后续能够直接筛选出首字母最大的子串，然后频率满足要求的字母组合起来成为新的串hot

接着我们求出hot全部子串的全排列，然后依次判断是否属于s，第一个满足要求的即为所求

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        num = Counter(s)
        hot = ''.join(ele * (num[ele] // k) for ele in sorted(num, reverse=True))
        for i in range(len(hot), 0, -1):
            for item in permutations(hot, i):
                word = ''.join(item)
                ss = iter(s)
                if all(c in ss for c in word * k):
                    return word
        return ''

注意在判断是否属于s时，利用iter()函数生成迭代器是个非常巧妙的选择，比直接for循环判断要更加简洁高效

 Comments
On this page
2014-重复 K 次的最长子序列