【贪心】【回溯】【字符串】2014. 重复 K 次的最长子序列-阿里云开发者社区

【贪心】【回溯】【字符串】2014. 重复 K 次的最长子序列

2024-04-10 21

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【贪心】【回溯】【字符串】2014. 重复 K 次的最长子序列

本文涉及知识点

贪心回溯字符串

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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。