Skip to content
TheChatArchiveThe Chat Archive
Qwenqwq-32b· Alibaba (Qwen)Hugging Face LMArena Human Preference 140K

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

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Kimikimi-k2-0711-preview’s answer.
  1. 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) {

    }
    

    }

  2. Qwen Assistant

    To solve this problem, we need to find the longest subsequence in a given string s that can be repeated k times and still be a subsequence of s. If there are multiple such subsequences, we choose the lexicographically largest one.

    Approach

    1. Preprocessing:

      • Calculate the frequency of each character in s.
      • Identify candidate characters that appear at least k times, as these are the only characters that can be part of the desired subsequence.
      • Store the positions of each character in s to facilitate efficient checking later.
    2. 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.
    3. Validation Check:

      • For each candidate subsequence, check if repeating it k times forms a valid subsequence of s using a helper function. This check uses binary search to efficiently find positions of characters in s.

    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

    1. 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.
    2. 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 k times and still be a valid subsequence of s.
    3. Validation Check:

      • For each candidate subsequence, we check if it can be repeated k times by ensuring each character's positions in s are correctly ordered. This is done efficiently using binary search to find the next valid position for each character.

    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.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.