What is the primary pattern to solve the Longest Subsequence Repeated k Times problem?

The primary pattern is backtracking search with pruning, which explores subsequences efficiently while eliminating unnecessary paths.

How does pruning help in the Longest Subsequence Repeated k Times problem?

Pruning reduces the search space by discarding subsequences that cannot possibly form a valid sequence repeated k times, improving efficiency.

What is the time complexity of the Longest Subsequence Repeated k Times problem?

The time complexity is O(n · ⌊n/k⌋!), where n is the length of the string and ⌊n/k⌋ is the upper bound on subsequence length.

How do you handle lexicographical order in this problem?

Use a greedy strategy to select the lexicographically largest subsequence when multiple subsequences of the same length are possible.

What does it mean for a subsequence to be repeated k times?

A subsequence is repeated k times if concatenating the subsequence k times results in a valid subsequence of the string s.

#2014

Hard

auto_awesome回溯·pruning

LeetCode 题解工作台

重复 K 次的最长子序列

给你一个长度为 n 的字符串 s ，和一个整数 k 。请你找出字符串 s 中重复 k 次的最长子序列。子序列是由其他字符串删除某些（或不删除）字符派生而来的一个字符串。如果 seq * k 是 s 的一个子序列，其中 seq * k 表示一个由 seq 串联 k 次构造的字符串，那么就称…

字符串回溯贪心计数枚举

题目描述

给你一个长度为 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 < min(2001, k * 8)
s 由小写英文字母组成

lightbulb

解题思路

方法一：BFS

我们可以先统计字符串中每个字符出现的次数，然后将出现次数大于等于 $k$ 的字符按从小到大的顺序存入一个列表 $\textit{cs}$ 中。接下来，我们可以使用 BFS 来枚举所有可能的子序列。

我们定义一个队列 $\textit{q}$ ，初始时将空字符串放入队列中。然后，我们从队列中取出一个字符串 $\textit{cur}$ ，并尝试将每个字符 $c \in \textit{cs}$ 添加到 $\textit{cur}$ 的末尾，形成一个新的字符串 $\textit{nxt}$ 。如果 $\textit{nxt}$ 是一个重复 $k$ 次的子序列，我们就将其加入到答案中，并将 $\textit{nxt}$ 放入队列中继续处理。

我们需要一个辅助函数 $\textit{check(t, k)}$ 来判断字符串 $\textit{t}$ 是否是字符串 $s$ 的一个重复 $k$ 次的子序列。具体地，我们可以使用两个指针来遍历字符串 $s$ 和 $\textit{t}$ ，如果在遍历过程中能够找到 $\textit{t}$ 的所有字符，并且能够重复 $k$ 次，那么就返回 $\textit{true}$ ，否则返回 $\textit{false}$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        def check(t: str, k: int) -> bool:
            i = 0
            for c in s:
                if c == t[i]:
                    i += 1
                    if i == len(t):
                        k -= 1
                        if k == 0:
                            return True
                        i = 0
            return False

        cnt = Counter(s)
        cs = [c for c in ascii_lowercase if cnt[c] >= k]
        q = deque([""])
        ans = ""
        while q:
            cur = q.popleft()
            for c in cs:
                nxt = cur + c
                if check(nxt, k):
                    ans = nxt
                    q.append(nxt)
        return ans

speed

复杂度分析

指标	值
时间	O(n \cdot {\lfloor \dfrac{n}{k} \rfloor}!)
空间	O(\lfloor \dfrac{n}{k} \rfloor!)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate identify the importance of pruning in reducing the search space?
question_mark
Does the candidate understand the relationship between subsequence length and k?
question_mark
How well does the candidate handle lexicographical ordering in the subsequence selection?

warning

常见陷阱

外企场景

error
Failing to prune search paths that cannot possibly yield valid subsequences.
error
Overlooking the lexicographical order requirement when multiple valid subsequences exist.
error
Incorrectly assuming the subsequence length can exceed n/k.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to find subsequences repeated m times for a different integer m.
arrow_right_alt
Change the problem to find the shortest subsequence repeated k times.
arrow_right_alt
Consider the case where the subsequence must be contiguous instead of a general subsequence.

help

常见问题

外企场景

继续练习

#2048 下一个更大的数值平衡数 #2131 连接两字母单词得到的最长回文串 #1849 将字符串拆分为递减的连续值