重复 K 次的最长子序列

/*
 * 思路：
 * 1. 使用回溯法生成所有可能的子序列，生成器函数使用流式编程。
 * 2. 对每一个子序列，检查其重复k次后是否仍为原字符串的子序列。
 * 3. 保存最长的符合条件的子序列，并在出现更长或者字典序更大的子序列时更新结果。
 */
import java.util.*;
import java.util.stream.*;

public class LongestRepeatingSubsequenceStream {
    public String longestSubsequenceRepeatedK(String s, int k) {
        String result = "";
        for (int len = 1; len <= s.length() / k; len++) {
            Set<String> subsequences = generateSubsequences(s, len).collect(Collectors.toSet());
            for (String subseq : subsequences) {
                if (isKTimesRepeatedSubsequence(s, subseq, k)) {
                    if (subseq.length() > result.length() || (subseq.length() == result.length() && subseq.compareTo(result) > 0)) {
                        result = subseq;
                    }
                }
            }
        }
        return result;
    }

    private Stream<String> generateSubsequences(String s, int len) {
        List<String> result = new ArrayList<>();
        generate(s, 0, len, new StringBuilder(), result);
        return result.stream();
    }

    private void generate(String s, int index, int len, StringBuilder current, List<String> result) {
        if (current.length() == len) {
            result.add(current.toString());
            return;
        }
        if (index >= s.length()) return;
        generate(s, index + 1, len, current, result);
        current.append(s.charAt(index));
        generate(s, index + 1, len, current, result);
        current.deleteCharAt(current.length() - 1);
    }

    private boolean isKTimesRepeatedSubsequence(String s, String subseq, int k) {
        int count = 0, j = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == subseq.charAt(j)) {
                j++;
                if (j == subseq.length()) {
                    j = 0;
                    count++;
                    if (count == k) return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        LongestRepeatingSubsequenceStream lrs = new LongestRepeatingSubsequenceStream();
        System.out.println(lrs.longestSubsequenceRepeatedK("letsleetcode", 2)); // 输出: "let"
        System.out.println(lrs.longestSubsequenceRepeatedK("bb", 2)); // 输出: "b"
        System.out.println(lrs.longestSubsequenceRepeatedK("ab", 2)); // 输出: ""
    }
}