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

作者推荐

map|动态规划|单调栈|LeetCode975:奇偶跳

涉及知识点

单调栈

题目

给你一个字符串 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

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

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

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用C++ 实现。