原文链接: https://leetcode-cn.com/problems/longest-subsequence-repeated-k-times

英文原文

You are given a string s of length n, and an integer k. You are tasked to find the longest subsequence repeated k times in string s.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

A subsequence seq is repeated k times in the string s if seq * k is a subsequence of s, where seq * k represents a string constructed by concatenating seq k times.

• For example, "bba" is repeated 2 times in the string "bababcba", because the string "bbabba", constructed by concatenating "bba" 2 times, is a subsequence of the string "bababcba".

Return the longest subsequence repeated k times in string s. If multiple such subsequences are found, return the lexicographically largest one. If there is no such subsequence, return an empty string.

 

Example 1:

Input: s = "letsleetcode", k = 2
Output: "let"
Explanation: There are two longest subsequences repeated 2 times: "let" and "ete".
"let" is the lexicographically largest one.

Example 2:

Input: s = "bb", k = 2
Output: "b"
Explanation: The longest subsequence repeated 2 times is "b".

Example 3:

Input: s = "ab", k = 2
Output: ""
Explanation: There is no subsequence repeated 2 times. Empty string is returned.

Example 4:

Input: s = "bbabbabbbbabaababab", k = 3
Output: "bbbb"
Explanation: The longest subsequence "bbbb" is repeated 3 times in "bbabbabbbbabaababab".

 

Constraints:

• n == s.length
• 2 <= n, k <= 2000
• 2 <= n < k * 8
• s consists of lowercase English letters.

中文题目

给你一个长度为 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 次的最长子序列。返回空字符串。

示例 4：

输入：s = "bbabbabbbbabaababab", k = 3
输出："bbbb"
解释：在 "bbabbabbbbabaababab" 中重复 3 次的最长子序列是 "bbbb" 。

 

提示：

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

通过代码

高赞题解

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

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

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循环判断要更加简洁高效

统计信息

通过次数	提交次数	AC比率
1513	2877	52.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言