本文涉及知识点
贪心 回溯 字符串
LeetCode2014. 重复 K 次的最长子序列
给你一个长度为 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：
example 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 < k * 8
s 由小写英文字母组成
回溯
因为n < k*8， 则最多7个字符。
string s1 记录 出现数量>=k次的字符。如果一个字符出现m× \times×k次，则记录m次。
枚举mask ∈ \in∈ [1,1 << s1.length()]。
for(int i= 0 ; i < s1.length();i++ ) { if(mask&(1<<i)) { s2 += s1[i]; } }
将s2 降序排序，计算是否存在k个为s2的子序列。如果有，直接返回；否则，用系统函数prev_permutation计算前一个字典序。
代码
核心代码
class Solution { public: string longestSubsequenceRepeatedK(string s, int k) { m_s = s; m_iK = k; int cnt[26] = { 0 }; for (const auto& ch : s) { cnt[ch - 'a']++; } string s1; for (int i = 0; i < 26; i++) { s1 += string(cnt[i] / k, 'a' + i); } const int n = s1.length(); for (int i = 1; i < (1 << n); i++) { string s2; for (int j = 0; j < n; j++) { if (i & (1 << j)) { s2 += s1[j]; } } Do(s2); } return m_res.empty() ? "" : m_res.rbegin()->second; } void Do(string& s2) { sort(s2.begin(), s2.end(), std::greater<>()); do { int cnt = 0; for (const auto& ch : m_s) { if (ch == s2[cnt % s2.length()]) { cnt++; } } if (cnt >= m_iK * s2.length()) { m_res.emplace(s2.length(), s2); if (m_res.size() > 1) { m_res.erase(m_res.begin()); } } } while (prev_permutation(s2.begin(), s2.end())); } set<pair<int, string>> m_res; string m_s; int m_iK; };
2023年5月版
class Solution { public: string longestSubsequenceRepeatedK(string s, int k) { m_s = s; m_c = s.length(); m_iK = k; m_vFreq.resize(26); for (const char&ch : s) { m_vFreq[ch - ‘a’]++; } for (int len = 7; len > 0; len–) { string str = dfs(“”, len); if (str.length()) { return str; } } return “”; } string dfs(string str,int leve) { if (0 == leve) { return Do(str)?str:“”; } for (int i = 25; i >= 0; i–) { if (m_vFreq[i] < m_iK) { continue; } m_vFreq[i] -= m_iK; string strRet = dfs(str + char(i + ‘a’), leve - 1); if (strRet.length()) { return strRet; } m_vFreq[i] += m_iK; } return “”; } bool Do(const string& strSub) { int iSBegin = 0; int i = 0, k =0; for (; iSBegin < m_c; iSBegin++) { if (strSub[i] == m_s[iSBegin]) { i++; } if (strSub.length() == i) { i = 0; k++; } if (m_iK == k) { return true; } } return false; } int m_c; string m_s; int m_iK; vector m_vFreq; };
2023年7月
class Solution { public: string longestSubsequenceRepeatedK(string s, int k) { m_c = s.length(); m_iK = k; m_s = s; m_vNums.assign(m_c+1, vector(26)); /* for (int i = m_c - 1; i >= 0; i–) { m_vNums[i] = m_vNums[i + 1]; m_vNums[i][s[i] - ‘a’]++; } / for (int i = 0; i < m_c; i++) { m_vIndexs[s[i] - ‘a’].emplace_back(i); } vector cur; int aUse[26] = { 0 }; dfs(cur, aUse, 0); return m_strRet; } void dfs(vector& cur,int aUse, int iCurIndex) { for (int i = 0; i < 26; i++) { const auto& v = m_vIndexs[i]; int index = std::lower_bound(v.begin(), v.end(), iCurIndex) - v.begin(); if (index >= v.size()) { continue; } cur.push_back(i); aUse[i]++; if (Check(cur, aUse, v[index] + 1)) { dfs(cur, aUse, v[index] + 1); } cur.pop_back(); aUse[i]–; } } bool Check(const vector& cur, int* aUse, int iCurIndex) { for (int i = 1; i < m_iK; i++) { for (const auto& ch : cur) { const auto& v = m_vIndexs[ch]; int index = std::lower_bound(v.begin(), v.end(), iCurIndex) - v.begin(); if (index >= v.size()) { return false; } iCurIndex = v[index] + 1; } } string ret; for (const auto& tmp : cur) { ret += ‘a’ + tmp; } if (ret.length() > m_strRet.length()) { m_strRet = ret; } else if (ret.length() == m_strRet.length()) { if (ret > m_strRet) { m_strRet = ret; } } return true; } int m_c; vector<vector> m_vNums; std::vector m_vIndexs[26]; int m_iK; string m_s; string m_strRet; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
