给你一个长度为 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
To solve this problem, we need to find the longest subsequence in a given string
sthat can be repeatedktimes and still be a subsequence ofs. If there are multiple such subsequences, we choose the lexicographically largest one.Approach
-
Preprocessing:
- Calculate the frequency of each character in
s. - Identify candidate characters that appear at least
ktimes, as these are the only characters that can be part of the desired subsequence. - Store the positions of each character in
sto facilitate efficient checking later.
- Calculate the frequency of each character in
-
Depth-First Search (DFS):
- Use DFS to explore possible subsequences starting from an empty string.
- At each step, try to extend the current subsequence by adding the lexicographically largest possible candidate character.
- Track the best solution (longest and lexicographically largest) found so far.
-
Validation Check:
- For each candidate subsequence, check if repeating it
ktimes forms a valid subsequence ofsusing a helper function. This check uses binary search to efficiently find positions of characters ins.
- For each candidate subsequence, check if repeating it
Solution Code
import java.util.*; class Solution { private String best = ""; public String longestSubsequenceRepeatedK(String s, int k) { int[] count = new int[26]; for (char c : s.toCharArray()) { count[c - 'a']++; } List<Character> candidates = new ArrayList<>(); for (char c = 'z'; c >= 'a'; c--) { if (count[c - 'a'] >= k) { candidates.add(c); } } if (candidates.isEmpty()) return ""; List<List<Integer>> pos = new ArrayList<>(26); for (int i = 0; i < 26; i++) { pos.add(new ArrayList<>()); } for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); pos.get(c - 'a').add(i); } int[] initialCounts = new int[26]; dfs("", initialCounts, candidates, count, k, pos); return best; } private void dfs(String curr, int[] counts, List<Character> candidates, int[] count, int k, List<List<Integer>> pos) { if (curr.length() > best.length() || (curr.length() == best.length() && curr.compareTo(best) > 0)) { best = curr; } // Prune if remaining possible characters can't improve the current best int remaining = 0; for (char c : candidates) { int idx = c - 'a'; remaining += (count[idx] / k - counts[idx]); } if (curr.length() + remaining <= best.length()) { return; } for (char c : candidates) { int idx = c - 'a'; if (counts[idx] < count[idx] / k) { counts[idx]++; String newCurr = curr + c; if (check(newCurr, k, pos)) { dfs(newCurr, counts.clone(), candidates, count, k, pos); } counts[idx]--; } } } private boolean check(String seq, int k, List<List<Integer>> pos) { int ptr = 0; for (int rep = 0; rep < k; rep++) { for (char c : seq.toCharArray()) { int idx = c - 'a'; List<Integer> list = pos.get(idx); int left = 0, right = list.size(); while (left < right) { int mid = (left + right) / 2; if (list.get(mid) < ptr) { left = mid + 1; } else { right = mid; } } if (left == list.size()) { return false; } ptr = list.get(left) + 1; } } return true; } }Explanation
-
Preprocessing:
- We count the occurrences of each character and filter out characters that cannot be part of the solution due to insufficient counts.
- We store the positions of each character to facilitate quick lookups during validation.
-
DFS Exploration:
- Starting with an empty string, we recursively try to extend the current subsequence by adding each candidate character in lexicographical order (from 'z' to 'a').
- We use a helper function to check if the new subsequence can be repeated
ktimes and still be a valid subsequence ofs.
-
Validation Check:
- For each candidate subsequence, we check if it can be repeated
ktimes by ensuring each character's positions insare correctly ordered. This is done efficiently using binary search to find the next valid position for each character.
- For each candidate subsequence, we check if it can be repeated
This approach ensures we explore the most promising candidates first (lexicographically largest) and prunes paths that cannot yield a better result than the current best, leading to an efficient solution.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.