这是一个经典的编程问题，可以用 单调栈 的方法高效解决。以下是解题步骤和代码实现：
问题描述
给定一个字符串 s 和一个整数 k，要求删除字符串中的一些字符，最终保留 k 个字符，且相对顺序不变，使得结果字符串字典序最小。
解题思路
-
单调栈维护最小字典序：
- 使用一个栈来维护当前最小的字典序字符。
- 遍历字符串
s，尝试将每个字符压入栈。 - 如果栈顶字符大于当前字符，并且后面还有足够的字符可以填满栈，则弹出栈顶字符。
- 最终栈中保留的就是字典序最小的字符。
-
边界条件：
- 栈的大小不能超过
k。 - 遍历时要确保剩下的字符足够填满栈（栈中已保留字符 + 剩余未处理字符 >=
k）。
- 栈的大小不能超过
Python代码实现
def removeToKeepKMin(s: str, k: int) -> str:
stack = [] # 用于存放最终结果字符的栈
n = len(s) # 字符串长度
for i, char in enumerate(s):
# 当栈非空，且栈顶字符比当前字符大，且后面还有足够字符时，可以弹出栈顶
while stack and stack[-1] > char and len(stack) + (n - i) > k:
stack.pop()
# 如果栈长度小于k，则可以压入当前字符
if len(stack) < k:
stack.append(char)
# 最终栈中的字符就是结果
return ''.join(stack)
示例
示例 1
s = "bcabc"
k = 3
print(removeToKeepKMin(s, k)) # 输出: "abc"
解释：
- 删除字符串中的第一个
'b'和第二个'c'，保留"abc"，使得字典序最小。
示例 2
s = "cbacdcbc"
k = 4
print(removeToKeepKMin(s, k)) # 输出: "acdb"
解释：
- 删除字符
'c'和'b'后，保留"acdb"，使得字典序最小。
复杂度分析
- 时间复杂度：O(n)，每个字符最多入栈一次，出栈一次。
- 空间复杂度：O(k)，栈的最大大小为
k。
这个问题也可以通过动态规划（DP）来解决。不过相较于单调栈，动态规划的时间复杂度和实现相对更复杂一些。
以下是动态规划的解法思路：
动态规划解法思路
状态定义
我们定义一个二维数组 dp[i][j] 表示从字符串的前 i 个字符中，选择 j 个字符所能获得的字典序最小的字符串。
i是字符串前缀长度；j是要保留的字符个数；dp[i][j]表示从前i个字符中选j个字符的最优解（字典序最小）。
状态转移
在遍历字符串的过程中，对于每个字符，我们有两种选择：
- 不选当前字符：如果不选当前字符，那么问题退化为从前
i-1个字符中选择j个字符，即dp[i][j] = dp[i-1][j]。 - 选当前字符：如果选当前字符，那么我们需要从前
i-1个字符中选择j-1个字符，再加上当前字符，即dp[i][j] = dp[i-1][j-1] + s[i-1]。
状态转移方程如下：
[
dp[i][j] = \min(dp[i-1][j], dp[i-1][j-1] + s[i-1])
]
边界条件
- 当
j == 0（不保留字符时），结果为空字符串：dp[i][0] = ""； - 当
i == 0且j > 0（字符串为空时，无法选择任何字符）：dp[0][j]不存在，为无穷大（不可达）。
最终结果
最后的答案是 dp[n][k]，其中 n 是字符串长度，k 是要保留的字符数。
动态规划代码实现
以下是基于上述思路的 Python 实现：
def removeToKeepKMinDP(s: str, k: int) -> str:
n = len(s)
# dp[i][j] 表示从前 i 个字符中选择 j 个字符的字典序最小字符串
dp = [["" for _ in range(k + 1)] for _ in range(n + 1)]
# 初始化边界条件
for i in range(n + 1):
dp[i][0] = "" # 选择 0 个字符时为空字符串
for j in range(1, k + 1):
dp[0][j] = "~" # 不可能从空字符串中选择字符，用 "~" 表示无穷大（字典序最大字符）
# 动态规划填表
for i in range(1, n + 1):
for j in range(1, k + 1):
# 如果不选当前字符
option1 = dp[i-1][j]
# 如果选当前字符
option2 = dp[i-1][j-1] + s[i-1] if j <= i else "~" # 保证 j <= i
# 取字典序最小的结果
dp[i][j] = min(option1, option2)
return dp[n][k]
示例
示例 1
s = "bcabc"
k = 3
print(removeToKeepKMinDP(s, k)) # 输出: "abc"
过程：
- 初始化
dp表：dp[i][0]初始化为""；dp[0][j]初始化为"~"。
- 填表，逐步从前缀中选择字符并更新最优解。
- 最终
dp[5][3] = "abc"。
示例 2
s = "cbacdcbc"
k = 4
print(removeToKeepKMinDP(s, k)) # 输出: "acdb"
时间复杂度
- 时间复杂度：O(n * k)，
n是字符串长度，k是需要保留的字符数。- 每个
dp[i][j]都取决于上一步的状态，因此需要遍历整个dp表。
- 每个
- 空间复杂度：O(n * k)，用于存储
dp表。
相比单调栈方法，动态规划的复杂度更高，但它提供了更通用的思路，能够很好地解决其他类似问题。
总结
- 如果问题的输入规模较小，可以使用动态规划方法。
- 如果需要更高效的实现，单调栈是更优的选择，时间复杂度为 O(n)，空间复杂度为 O(k)。
