【单调栈】LeetCode2030:含特定字母的最小子序列-阿里云开发者社区

题目

给你一个字符串 s ，一个整数 k ，一个字母 letter 以及另一个整数 repetition 。

返回 s 中长度为 k 且字典序最小的子序列，该子序列同时应满足字母 letter 出现至少 repetition 次。生成的测试用例满足 letter 在 s 中出现至少 repetition 次。

子序列是由原字符串删除一些（或不删除）字符且不改变剩余字符顺序得到的剩余字符串。

字符串 a 字典序比字符串 b 小的定义为：在 a 和 b 出现不同字符的第一个位置上，字符串 a 的字符在字母表中的顺序早于字符串 b 的字符。

示例 1：

输入：s = “leet”, k = 3, letter = “e”, repetition = 1

输出：“eet”

解释：存在 4 个长度为 3 ，且满足字母 ‘e’ 出现至少 1 次的子序列：

“lee”（“leet”）
“let”（“leet”）
“let”（“leet”）
“eet”（“leet”）
其中字典序最小的子序列是 “eet” 。
示例 2：
输入：s = “leetcode”, k = 4, letter = “e”, repetition = 2
输出：“ecde”
解释：“ecde” 是长度为 4 且满足字母 “e” 出现至少 2 次的字典序最小的子序列。
示例 3：
输入：s = “bb”, k = 2, letter = “b”, repetition = 2
输出：“bb”
解释：“bb” 是唯一一个长度为 2 且满足字母 “b” 出现至少 2 次的子序列。
参数范围：
1 <= repetition <= k <= s.length <= 5 * 10⁴
s 由小写英文字母组成
letter 是一个小写英文字母，在 s 中至少出现 repetition 次

单调栈

最简单的情况：不限制长度和重复字符

从左到右将s[i]放到栈中，放入之前向将栈中大于s[i]的出栈。下面来证明：

假定s的最小子系列的为依次为：{i1,i2,i3…}。

规则一：i1之前没有数小于等于它。否则将此数的放在最前会变得最小。

规则二：i1之后没有数小于它，否则替换i1会变得更小。

规则三：i1和i2之间没有数小于等于i2。

规则四：i2之后没有数小于它，否则替换i2会变得更小。

…

栈底到栈顶就是最小子系列。

i1在栈底，说明它前面的数都大于它，所以出栈了。

i1没有出栈，说明i1之后没有数比它小，否则i1出栈了。

i2之前，i1之后没有数据，说明两者之间没有数小于等于i2，否则不会出栈。

i2没有出栈说明之后没有数据小于它，否则出栈了。

…

大数出栈后，变成前面的数小，后面的数大。也就是递增的单调栈。

注意: {1,1,1} 前面增加1，变成{1,1,1,1} 有些规则可能变小，有些规则可能变大。

限制长度k

限制了长度，也就限制了出栈次数。前面的数变小比后面的数变小更小，所以把出栈的机会留给前面。

出栈的时候增加判断：如果出栈后，使得长度一定少于k则不出栈。

入栈的时候增加判断：如果长度已经为k，则不入栈。

必须特定个特定字母

如果出栈会造成特定字母不足则不出栈。

入栈时增加处理：如果长度为k，但当前是特定字母，不入栈则特定字母不足，出栈栈顶所有特定字母，直到非特定字母。出栈它，把出栈的特定字母和当前字母入栈。这个操作在超时的边缘。

代码

核心代码

class Solution {
public:
  string smallestSubsequence(const string s, const int k, const char letter, const int repetition) {
    int iCanOutCount = std::count(s.begin(), s.end(), letter) - repetition;//可以不使用letter的数量
    vector<char> sta;
    for (int i = 0; i < s.length(); i++)
    {
      const auto& ch = s[i];
      auto NeedPop = [&]()
      {
        if (sta.empty() || (sta.size() + s.length() - i <= k) || (sta.back() <= ch))
        {
          return false;
        }
        if ((sta.back() == letter) && (iCanOutCount <= 0))
        {
          return false;
        }
        return true;
      };
      while (NeedPop())
      {
        iCanOutCount -= (sta.back() == letter);
        sta.pop_back();
      }
      if (sta.size() < k)
      {
        sta.emplace_back(ch);
      }
      else if ((letter == ch)&&( iCanOutCount <= 0 ))
      {
        int iCnt = 1;
        while (sta.size()+ iCnt > k )
        {
          if (letter == sta.back())
          {
            iCnt++;
          }
          sta.pop_back();
        }
        while (iCnt--)
        {
          sta.emplace_back(letter);
        }
      }
      else
      {
        iCanOutCount -= (letter == ch);
      }
    }
    sta.emplace_back(0);
    return sta.data();
  }
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  string s;
  int k;
  char letter;
  int repetition;
  {
    Solution slu;
    s = "leet", k = 3, letter = 'e', repetition = 1;
    auto res = slu.smallestSubsequence(s, k, letter, repetition);
    Assert(std::string("eet"), res);
  }
  {
    Solution slu;
    s = "leetcode", k = 4, letter = 'e', repetition = 2;
    auto res = slu.smallestSubsequence(s, k, letter, repetition);
    Assert(std::string("ecde"), res);
  }
  {
    Solution slu;
    s = "bb", k = 2, letter ='b', repetition = 2;
    auto res = slu.smallestSubsequence(s, k, letter, repetition);
    Assert(std::string("bb"), res);
  }
  {
    Solution slu;
    s = "aaabbbcccddd", k = 3, letter = 'b', repetition = 2;
    auto res = slu.smallestSubsequence(s, k, letter, repetition);
    Assert(std::string("abb"), res);
  }
  {
    Solution slu;
    s = "hjjhhhmhhwhz", k = 6, letter = 'h', repetition = 5;
    auto res = slu.smallestSubsequence(s, k, letter, repetition);
    Assert(std::string("hhhhhh"), res);
  }
  //CConsole::Out(res);
}

优化

非特定字母最多入栈：k - repetition。注意：非特定字母入栈的时候，也要判断栈的长度小于k。

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  string s;
  int k;
  char letter;
  int repetition;
  {
    Solution slu;
    s = "leet", k = 3, letter = 'e', repetition = 1;
    auto res = slu.smallestSubsequence(s, k, letter, repetition);
    Assert(std::string("eet"), res);
  }
  {
    Solution slu;
    s = "leetcode", k = 4, letter = 'e', repetition = 2;
    auto res = slu.smallestSubsequence(s, k, letter, repetition);
    Assert(std::string("ecde"), res);
  }
  {
    Solution slu;
    s = "bb", k = 2, letter ='b', repetition = 2;
    auto res = slu.smallestSubsequence(s, k, letter, repetition);
    Assert(std::string("bb"), res);
  }
  {
    Solution slu;
    s = "aaabbbcccddd", k = 3, letter = 'b', repetition = 2;
    auto res = slu.smallestSubsequence(s, k, letter, repetition);
    Assert(std::string("abb"), res);
  }
  {
    Solution slu;
    s = "hjjhhhmhhwhz", k = 6, letter = 'h', repetition = 5;
    auto res = slu.smallestSubsequence(s, k, letter, repetition);
    Assert(std::string("hhhhhh"), res);
  }
  //CConsole::Out(res);
}

2023年3月旧版

class Solution {
public:
string smallestSubsequence(string s, int k, const char letter, int repetition) {
m_c = s.length();
int iCanNotUseLetterNum = -repetition;//可以不使用letter多少次
int iCanNotUseChar = m_c - k;
vector vAns;
for (const auto& ch : s)
{
if (ch == letter)
{
iCanNotUseLetterNum++;
}
}
for (int i = 0; i < m_c; i++)
{
const auto& ch = s[i];
while (vAns.size() && (ch < vAns.back()) && iCanNotUseChar && ((letter != vAns.back()) || iCanNotUseLetterNum))
{
if (letter == vAns.back())
{
iCanNotUseLetterNum–;
}
iCanNotUseChar–;
vAns.pop_back();
}
vAns.push_back(ch);
}
string strRet;
for (int iIndex = vAns.size() - 1; iIndex >= 0; iIndex–)
{
const char& ch = vAns[iIndex];
if (0 == iCanNotUseChar)
{
strRet += ch;
continue;
}
if (letter == ch )
{
if (iCanNotUseLetterNum)
{
iCanNotUseLetterNum–;
iCanNotUseChar–;
}
else
{
strRet += ch;
}
}
else
{
iCanNotUseChar–;
}
}
vector tmp(strRet.rbegin(), strRet.rend());
tmp.push_back(0);
return tmp.data();
}
int m_c;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步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++ 实现。

【单调栈】LeetCode2030:含特定字母的最小子序列

题目

单调栈