java 解法, 执行用时: 452 ms, 内存消耗: 43.3 MB, 提交时间: 2023-09-17 12:05:12

class Solution 
{
    String s;
    int sn;
    int k;

    public boolean check(String t)
    {
        int tn = t.length();
        int cnt = 0;
        int ti = 0;
        for (int i = 0; i < sn; i ++)
        {
            //----剪枝，即使剩下的全都匹配。也不够长了。
            int need_n = (k - cnt) * tn - ti - 1;
            if (need_n > (sn - i - 1))
                return false;
            //----尝试匹配
            if (s.charAt(i) == t.charAt(ti))
            {
                ti ++;
                if (ti == tn)
                {
                    cnt ++;
                    ti = 0;
                    if (cnt == k)
                        return true;
                }
            }
        }
        return false;
    }


    public String longestSubsequenceRepeatedK(String s, int k) 
    {
        this.s = s;
        this.sn = s.length();
        this.k = k;

        List<List<String>> len_subs = new ArrayList<>();
        for (int i = 0; i < 8; i ++)
            len_subs.add(new ArrayList<>());
        len_subs.get(0).add(new String(""));
        for (int i = 0; i < 7; i ++)
        {
            for (String t : len_subs.get(i))
            {
                for (int x = 0; x < 26; x ++)
                {
                    String r = t + (char)('a' + x);
                    if (check(r) == true)
                    {
                        len_subs.get(i + 1).add(r);
                    }
                }
            }
        }

        for (int i = 7; i > -1; i --)
        {
            if (len_subs.get(i).size() > 0)
            {
                return len_subs.get(i).get(len_subs.get(i).size() - 1);
            }
        }
        return new String("");
    }
}

python3 解法, 执行用时: 1948 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-17 12:03:50

class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        num = Counter(s)
        hot = ''.join(ele * (num[ele] // k) for ele in sorted(num, reverse=True))
        for i in range(len(hot), 0, -1):
            for item in permutations(hot, i):
                word = ''.join(item)
                ss = iter(s)
                if all(c in ss for c in word * k):
                    return word
        return ''

cpp 解法, 执行用时: 236 ms, 内存消耗: 52.1 MB, 提交时间: 2023-09-17 12:03:27

class Solution {
public:
    string longestSubsequenceRepeatedK(string s, int k) {
        // n < k * 8 ：答案的最大长度为 7
        int n = s.length();
        vector<vector<int>> nxt(n+1);
        vector<int> pos(26, n+1);
        for(int i = n; ~i; --i) {
            nxt[i] = pos;
            if(i)   pos[s[i-1]-'a'] = i;
        }

        auto check = [&](string p) {
            int i = 0;
            for(int cnt = 0; cnt < k; ++cnt) {
                for(int j = 0; j < p.length(); ++j) {
                    i = nxt[i][p[j]-'a'];
                    if(i == n + 1)  return false;
                }
            }
            return true;            
        };

        vector<string> ans[8];
        ans[0].push_back(""); 
        for(int len = 1; len < 8; ++len) {
            for(auto t : ans[len-1]) {
                for(char c = 'a'; c <= 'z'; ++c) {
                    string p = t + c;
                    if(check(p))    ans[len].push_back(p);
                }
            }
        }

        for(int i = 7; ~i; --i) {
            if(ans[i].size() == 0)  continue;
            return ans[i].back();
        }
        return "";
    }
};

golang 解法, 执行用时: 92 ms, 内存消耗: 7.5 MB, 提交时间: 2023-09-17 12:02:58

/**
 * 我们可以统计出 s 中个数不低于 k 的字符，答案只能由这些字符组成，
 * 而这些字符的个数不会超过 n/k，由于 n<8k，故字符个数不超过 7。
 * 由于字符个数很小，我们暴力枚举这些字符的所有子集的所有排列，
 * 然后尽可能多地匹配 s 中的字符串，从中找到符合题目要求的子序列。
 */
func longestSubsequenceRepeatedK(s string, k int) (ans string) {
	n := len(s)
	pos := [26]int{}
	for i := range pos {
		pos[i] = n
	}
	nxt := make([][26]int, n)
	cnt := [26]int{}
	for i := n - 1; i >= 0; i-- {
		nxt[i] = pos
		pos[s[i]-'a'] = i
		cnt[s[i]-'a']++
	}

	// 计算所有可能出现在答案中的字符，包括重复的
	// 倒着统计，这样下面计算排列时的第一个合法方案就是答案，从而提前退出
	a := []byte{}
	for i := 25; i >= 0; i-- {
		for c := cnt[i]; c >= k; c -= k {
			a = append(a, 'a'+byte(i))
		}
	}

	for m := len(a); m > 0 && ans == ""; m-- { // 从大到小枚举答案长度 m
		permutations(len(a), m, func(ids []int) bool { // 枚举长度为 m 的所有排列
			t := make([]byte, m)
			for i, id := range ids {
				t[i] = a[id]
			}
			i, j := 0, 0
			if t[0] == s[0] {
				j = 1
			}
			for {
				i = nxt[i][t[j%m]-'a']
				if i == n {
					break
				}
				j++
			}
			if j >= k*m {
				ans = string(t)
				return true // 提前退出
			}
			return false
		})
	}
	return
}

// 模板：生成 n 选 r 的排列
func permutations(n, r int, do func(ids []int) bool) {
	ids := make([]int, n)
	for i := range ids {
		ids[i] = i
	}
	if do(ids[:r]) {
		return
	}
	cycles := make([]int, r)
	for i := range cycles {
		cycles[i] = n - i
	}
	for {
		i := r - 1
		for ; i >= 0; i-- {
			cycles[i]--
			if cycles[i] == 0 {
				tmp := ids[i]
				copy(ids[i:], ids[i+1:])
				ids[n-1] = tmp
				cycles[i] = n - i
			} else {
				j := cycles[i]
				ids[i], ids[n-j] = ids[n-j], ids[i]
				if do(ids[:r]) {
					return
				}
				break
			}
		}
		if i == -1 {
			return
		}
	}
}