本文主要是介绍力扣-2904最短且字典序最小的美丽子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给你一个二进制字符串 s 和一个正整数 k 。
如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。
令 len 等于 最短 美丽子字符串的长度。
返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。
对于相同长度的两个字符串 a 和 b ，如果在 a 和 b 出现不同的第一个位置上，a 中该位置上的字符严格大于 b 中的对应字符，则认为字符串 a 字典序 大于 字符串 b 。
- 例如，
"abcd"的字典序大于"abcc"，因为两个字符串出现不同的第一个位置对应第四个字符，而d大于c。
示例 1：
输入：s = "100011001", k = 3 输出："11001" 解释：示例中共有 7 个美丽子字符串： 1. 子字符串 "100011001" 。 2. 子字符串 "100011001" 。 3. 子字符串 "100011001" 。 4. 子字符串 "100011001" 。 5. 子字符串 "100011001" 。 6. 子字符串 "100011001" 。 7. 子字符串 "100011001" 。 最短美丽子字符串的长度是 5 。 长度为 5 且字典序最小的美丽子字符串是子字符串 "11001" 。
示例 2：
输入：s = "1011", k = 2 输出："11" 解释：示例中共有 3 个美丽子字符串： 1. 子字符串 "1011" 。 2. 子字符串 "1011" 。 3. 子字符串 "1011" 。 最短美丽子字符串的长度是 2 。 长度为 2 且字典序最小的美丽子字符串是子字符串 "11" 。
示例 3：
输入：s = "000", k = 1 输出："" 解释：示例中不存在美丽子字符串。
提示：
1 <= s.length <= 1001 <= k <= s.length
分析问题：
由题意知，s是由0,1组成的字符串，要在这个长字符串里面找子序列，使得该子序列里面1的个数等于k，那么首先我们要排除k大于s中所有1的个数，这时候直接return空字符串，否则我们去找所有的1，最美子序列的第一个数字一定是1，那么就可以进行s.count('1')-n+1个循环，去遍历所有的可能性，起始值是s中第一个1的下标，遍历过去就把这个1变成0，以便我们继续使用index函数。把所有可能性放进列表里面，筛选出长度最短的最美子序列以int类型放入另一个列表里面，方便我们进行比大小。然后输出最小的最短最美子序列，注意输出要求是字符串类型，还需将其转为str类型输出。
代码实现：
class Solution:def shortestBeautifulSubstring(self, s: str, k: int) -> str:v=''if s.count('1') <k: return vn=len(s)a_min=101 # 最小长度dp=[0]*(n+5)ls=[]for q in range(n):if s[q]=='1':dp[q]=1b=dp.count(1)for i in range(b-k+1):a=dp.index(1)+1kk=a-1v='1'l=1while l<k:if dp[a]==1:v+='1'l+=1else: v+='0'a+=1dp[kk]=0if len(v)<=a_min: a_min=len(v)ls.append(v)last=len(ls[-1])li=[]for w in ls:if len(w)==last: li.append(int(w))if len(li)==1: return str(li[0])return str(min(li))总结：
首先对字符串 s 进行遍历，统计字符串 s 中 1 的数量并将结果存储在 dp 数组中。然后从 dp 数组中找出第一个出现 1 的位置，并依次向后构建长度为 k 的子串，判断子串的长度是否小于当前已找到的最小长度。如果是，则更新最小长度，并将当前子串长度和子串本身存储下来。最后对符合条件的子串进行筛选，返回最小的子串。
这篇关于力扣-2904最短且字典序最小的美丽子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
