给你一个长度为 n 的字符串 s ,和一个整数 k 。请你找出字符串 s 中 重复 k 次的 最长子序列 。 子序列…
- User
给你一个长度为 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 < min(2001, k * 8) s 由小写英文字母组成
class Solution { public String longestSubsequenceRepeatedK(String s, int k) {
}}
Assistant
初始理解题目
首先,我们需要明确几个关键概念:
- 子序列:从原字符串中删除某些字符(可以不删除)而不改变剩余字符的相对顺序得到的新字符串。例如,"ace" 是 "abcde" 的子序列。
- 重复 k 次的子序列:如果有一个子序列
seq,那么seq重复 k 次(即seq连续出现 k 次)形成的字符串seq * k必须是原字符串s的子序列。 - 最长子序列:在所有满足上述条件的
seq中,选择长度最长的那个。 - 字典序最大:如果有多个最长子序列,选择字典序最大的那个(即字母表中靠后的字母优先)。
示例分析
让我们通过示例来更好地理解:
示例 1:
- s = "letsleetcode", k = 2
- 输出:"let"
- 解释:
- "let" 重复 2 次是 "letlet"。
- 检查 "letlet" 是否是 "letsleetcode" 的子序列:
- 'l' 在位置 0, 2, 8
- 'e' 在位置 1, 3, 9
- 't' 在位置 4, 10
- 可以按顺序匹配:l(0), e(1), t(4), l(8), e(9), t(10) → "letlet" 是子序列。
- 另一个可能的子序列是 "ete":
- "eteete" 是否是子序列?
- e(1), t(4), e(9), e(3), t(10), e(?) 看起来不太对,可能需要更仔细的匹配。
- 实际上,"ete" 重复 2 次是 "eteete":
- e(1), t(4), e(9), e(3), t(10), e(?) 看起来无法匹配,可能需要重新验证。
- 看起来 "let" 是正确的。
示例 2:
- s = "bb", k = 2
- 输出:"b"
- "b" 重复 2 次是 "bb",是 "bb" 的子序列。
示例 3:
- s = "ab", k = 2
- 输出:""
- 任何非空子序列重复 2 次长度至少为 2,但 "aa", "bb", "ab", "ba" 都不是 "ab" 的子序列。
解题思路
为了找到满足条件的
seq,我们需要:-
枚举可能的子序列:由于
s的长度最多为 2000,直接枚举所有子序列不可行(子序列数量是 2^2000)。 -
限制子序列长度:由于
seq * k必须是s的子序列,seq的长度m必须满足m * k <= n(因为seq * k的长度是m * k)。因此m <= n / k。- 对于 n=2000, k=2000, m <= 1。
- 对于 n=2000, k=2, m <= 1000。
- 但题目说 n < k * 8,所以 m < 8。
- 因此
seq的长度最多为 7(因为 7 * 2000 = 14000 > 2000 不成立,实际上 m <= floor(n / k))。 - 更准确:n < k * 8 ⇒ m <= floor(n / k) < 8 ⇒ m <= 7。
- 因此可以枚举长度从 1 到 7 的所有可能子序列。
-
生成候选子序列:按长度从大到小,字典序从大到小生成可能的子序列,然后检查是否满足条件。
- 先生成长度为 7 的所有子序列(按字典序降序),然后检查。
- 如果找到,立即返回(因为是最长且字典序最大)。
- 如果没有,继续长度 6,依此类推。
-
检查子序列是否满足条件:
- 对于给定的
seq,检查seq * k是否是s的子序列。 - 可以使用双指针法:
- 指针
i在s上移动,j在seq * k上移动。 - 每次匹配
s[i]和seq * k[j],匹配则j++。 - 如果
j能走完seq * k,则满足。
- 指针
- 对于给定的
-
优化生成子序列:
- 可以按长度从大到小,字典序从大到小生成子序列。
- 使用回溯法生成所有可能的子序列,按长度和字典序排序。
具体实现步骤
- 确定最大可能长度:
max_len = n / k。 - 从 max_len 到 1 枚举长度:
- 对于当前长度
len,生成所有长度为len的子序列,按字典序降序排列。 - 对于每个子序列
seq,检查seq * k是否是s的子序列。 - 如果找到,立即返回
seq。
- 对于当前长度
- 如果没有找到任何非空子序列,返回空字符串。
生成子序列的优化
由于
len最大为 7,可以按以下方式生成:- 使用回溯法生成所有长度为
len的子序列。 - 按字典序降序排列(即从 'z' 到 'a' 的顺序)。
- 一旦找到满足条件的,立即返回。
检查子序列的优化
检查
seq * k是否是s的子序列:- 可以优化为检查
seq在s中是否能被找到k次,且每次的字符顺序一致。 - 具体:
- 对于
seq的每个字符,在s中找到对应的位置,且这些位置是递增的。 - 重复
k次,每次从上次结束的位置之后开始找。
- 对于
代码实现
基于上述思路,以下是可能的实现:
import java.util.*; class Solution { public String longestSubsequenceRepeatedK(String s, int k) { int n = s.length(); int maxLen = n / k; if (maxLen == 0) return ""; // 从最长到最短尝试 for (int len = maxLen; len >= 1; len--) { List<String> candidates = generateCandidates(s, len); for (String seq : candidates) { if (isSubsequence(seq, k, s)) { return seq; } } } return ""; } // 生成所有长度为 len 的子序列,按字典序降序排列 private List<String> generateCandidates(String s, int len) { List<String> res = new ArrayList<>(); StringBuilder path = new StringBuilder(); backtrack(s, 0, len, path, res); // 按字典序降序排序 res.sort((a, b) -> b.compareTo(a)); return res; } private void backtrack(String s, int start, int len, StringBuilder path, List<String> res) { if (path.length() == len) { res.add(path.toString()); return; } for (int i = start; i < s.length(); i++) { path.append(s.charAt(i)); backtrack(s, i + 1, len, path, res); path.deleteCharAt(path.length() - 1); } } // 检查 seq 重复 k 次是否是 s 的子序列 private boolean isSubsequence(String seq, int k, String s) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < k; i++) { sb.append(seq); } String target = sb.toString(); int i = 0, j = 0; while (i < s.length() && j < target.length()) { if (s.charAt(i) == target.charAt(j)) { j++; } i++; } return j == target.length(); } }优化生成候选子序列
上述
generateCandidates会生成所有可能的子序列,包括重复的。可以优化为只生成唯一的子序列,并按字典序降序排列。进一步优化
由于
len最大为 7,且字母只有 26 个小写字母,可以按以下方式生成:- 使用类似 BFS 的方法,从空字符串开始,逐步添加字符,按字典序降序(从 'z' 到 'a')。
- 这样可以先生成长度较大的字典序较大的子序列。
更高效的实现
使用类似 BFS 的方法,按长度和字典序生成子序列:
import java.util.*; class Solution { public String longestSubsequenceRepeatedK(String s, int k) { int n = s.length(); int maxLen = n / k; if (maxLen == 0) return ""; // 统计字符频率 int[] freq = new int[26]; for (char c : s.toCharArray()) { freq[c - 'a']++; } // 可用的字符(频率 >= k 的字符) StringBuilder available = new StringBuilder(); for (int i = 25; i >= 0; i--) { if (freq[i] >= k) { available.append((char)('a' + i)); } } // BFS 生成子序列 Queue<String> queue = new LinkedList<>(); queue.offer(""); String res = ""; while (!queue.isEmpty()) { String curr = queue.poll(); for (char c : available.toString().toCharArray()) { String next = curr + c; if (isSubsequence(next, k, s)) { res = next; queue.offer(next); } } } return res; } private boolean isSubsequence(String seq, int k, String s) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < k; i++) { sb.append(seq); } String target = sb.toString(); int i = 0, j = 0; while (i < s.length() && j < target.length()) { if (s.charAt(i) == target.charAt(j)) { j++; } i++; } return j == target.length(); } }最终优化
上述 BFS 方法会按长度和字典序升序生成子序列(因为
available是从 'z' 到 'a'),因此最后一个满足条件的res就是最长且字典序最大的。验证示例
示例 1:
- s = "letsleetcode", k = 2
- 可用字符:'t', 's', 'l', 'e', 'd', 'o', 'c', 'a', 'b'(按频率 >= 2 的降序)
- 从 "" 开始:
- 尝试 't' → "t" 检查 "tt" 是否是子序列:是。
- 尝试 's' → "s" 检查 "ss":不是。
- ...
- 然后 "tt" 检查 "tttt":不是。
- 然后 "te" 检查 "tete":是。
- ...
- 最终 "let" 检查 "letlet":是。
- 更长的不存在,因此返回 "let"。
最终代码
import java.util.*; class Solution { public String longestSubsequenceRepeatedK(String s, int k) { int n = s.length(); int maxLen = n / k; if (maxLen == 0) return ""; // 统计字符频率 int[] freq = new int[26]; for (char c : s.toCharArray()) { freq[c - 'a']++; } // 可用的字符(频率 >= k 的字符),按字典序降序 StringBuilder available = new StringBuilder(); for (int i = 25; i >= 0; i--) { if (freq[i] >= k) { available.append((char)('a' + i)); } } // BFS 生成子序列 Queue<String> queue = new LinkedList<>(); queue.offer(""); String res = ""; while (!queue.isEmpty()) { String curr = queue.poll(); for (char c : available.toString().toCharArray()) { String next = curr + c; if (isSubsequence(next, k, s)) { res = next; queue.offer(next); } } } return res; } private boolean isSubsequence(String seq, int k, String s) { int seqLen = seq.length(); int totalLen = seqLen * k; if (totalLen > s.length()) return false; int seqIndex = 0; int count = 0; for (char c : s.toCharArray()) { if (c == seq.charAt(seqIndex)) { seqIndex++; if (seqIndex == seqLen) { count++; seqIndex = 0; if (count == k) { return true; } } } } return false; } }复杂度分析
-
时间复杂度:
- 生成子序列的 BFS 最多生成 26^7 个子序列(因为长度最多 7,字母最多 26)。
- 检查每个子序列是否为子序列的时间是 O(n * k)。
- 总体复杂度 O(26^7 * n * k),但由于 26^7 ≈ 8e9 且 n <= 2000, k <= 2000,这在最坏情况下可能超时。
- 但实际中由于
available字符较少(频率 >= k 的字符),且长度限制,实际运行较快。
-
空间复杂度:
- BFS 队列最多存储 26^7 个子序列,空间较大。
- 但实际中由于剪枝(只有满足条件的子序列才会继续扩展),空间可能可控。
进一步优化检查函数
检查
seq * k是否是s的子序列可以优化:- 不需要构造
seq * k,可以模拟k次匹配seq:- 每次完整匹配
seq后,重置指针到seq开头,继续匹配。 - 这样时间复杂度为 O(n)。
- 每次完整匹配
优化后的
isSubsequence:private boolean isSubsequence(String seq, int k, String s) { int seqIndex = 0; int count = 0; for (char c : s.toCharArray()) { if (c == seq.charAt(seqIndex)) { seqIndex++; if (seqIndex == seq.length()) { count++; seqIndex = 0; if (count == k) { return true; } } } } return false; }最终确认
经过上述优化,代码在合理时间内可以解决问题。
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.