LeetCode 题解工作台
最短且字典序最小的美丽子字符串
给你一个二进制字符串 s 和一个正整数 k 。 如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。 令 len 等于 最短 美丽子字符串的长度。 返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。 …
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 滑动窗口（状态滚动更新）
答案摘要
我们可以枚举所有子字符串 $s[i: j]$，其中 $i \lt j$，并检查它们是否是美丽子字符串。如果是，我们就更新答案。 时间复杂度 ，空间复杂度 。其中 是字符串 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
给你一个二进制字符串 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
解题思路
方法一：枚举
我们可以枚举所有子字符串 ，其中 ，并检查它们是否是美丽子字符串。如果是，我们就更新答案。
时间复杂度 ，空间复杂度 。其中 是字符串 的长度。
class Solution:
def shortestBeautifulSubstring(self, s: str, k: int) -> str:
n = len(s)
ans = ""
for i in range(n):
for j in range(i + k, n + 1):
t = s[i:j]
if t.count("1") == k and (
not ans or j - i < len(ans) or (j - i == len(ans) and t < ans)
):
ans = t
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) for the sliding window iteration over s, with constant time updates for counting ones. Space complexity is O(1) aside from storing the substring result since only counts and pointers are maintained. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Looking for efficient substring tracking using a sliding window.
- question_mark
Check if candidate substrings maintain exactly k ones.
- question_mark
Expect consideration of lexicographical comparison during candidate updates.
常见陷阱
外企场景- error
Forgetting to shrink the window after reaching k ones, leading to longer substrings.
- error
Comparing substrings only by length and ignoring lexicographic order.
- error
Incorrectly counting ones when the window moves, causing invalid candidates.
进阶变体
外企场景- arrow_right_alt
Find the longest beautiful substring instead of the shortest, keeping lexicographic minimization.
- arrow_right_alt
Change s to contain characters beyond binary and count a different target character.
- arrow_right_alt
Return all shortest beautiful substrings rather than a single lexicographically smallest one.