M2904.最短且字典序最小的美丽子字符串

sliding window, https://leetcode.cn/problems/shortest-and-lexicographically-smallest-beautiful-string/

给你一个二进制字符串 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 <= 100
• 1 <= k <= s.length

题目描述

给你一个二进制字符串 s（仅包含 '0' 和 '1'）和一个正整数 k。

• 美丽子字符串：如果一个子字符串中 '1' 的个数恰好等于 k，则称其为美丽子字符串。
• 目标：在所有美丽子字符串中，找出长度最短的一个。如果有多个长度相同的最短美丽子字符串，返回其中字典序最小的一个。
• 如果不存在，返回空字符串 ""。

数据范围：字符串长度 $1\le s.length\le 100$，这说明算法的效率要求不是特别苛刻，但滑动窗口是最优解法。

---

解题思路：滑动窗口 (Sliding Window)

由于我们要寻找包含固定数量 '1' 的子字符串，滑动窗口是非常高效的选择。

1. 初始化：使用两个指针 left 和 right 表示窗口边界，变量 cnt1 记录当前窗口内 '1' 的个数。
2. 移动右边界：不断向右移动 right，如果遇到 '1'，则 cnt1 += 1。
3. 缩小左边界：当 cnt1 == k 时，尝试缩小窗口：
   • 如果 s[left] == '0'，缩小左边界不会改变 '1' 的数量，且能让字符串更短，所以直接 left += 1。
   • 直到窗口左端 s[left] 是 '1'，此时窗口不能再缩小了（再缩小 '1' 的数量就少于 k 了）。
4. 记录结果：
   • 在 cnt1 == k 的状态下，当前窗口 s[left:right+1] 就是一个候选的美丽子字符串。
   • 比较当前子串的长度。如果比之前找到的更短，则更新最优解；如果长度相等，则取字典序更小的一个。
5. 继续循环：直到 right 遍历完整个字符串。

---

Python 实现

class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        # 如果总的 '1' 个数都不够 k，直接返回空
        if s.count('1') < k:
            return ""
        
        n = len(s)
        res = ""
        cnt1 = 0
        left = 0
        
        for right in range(n):
            if s[right] == '1':
                cnt1 += 1
            
            # 当窗口内 '1' 的个数等于 k 时
            while cnt1 == k:
                # 尝试收缩左边界，去掉前导 '0'
                if s[left] == '1':
                    # 此时已经找到了一个包含 k 个 '1' 且以 '1' 开头和结尾的候选子串
                    current_str = s[left : right + 1]
                    
                    # 更新结果：如果更短，或者长度相同但字典序更小
                    if res == "" or len(current_str) < len(res) or (len(current_str) == len(res) and current_str < res):
                        res = current_str
                    
                    # 准备移动左指针，此时 cnt1 会减 1，跳出 while 循环
                    cnt1 -= 1
                
                left += 1
                
        return res

---

复杂度分析

• 时间复杂度：$O(N^2)$。
  • 虽然窗口指针 left 和 right 都只移动了 $N$ 次（双指针 $O(N)$），但在更新 res 时，提取字符串 s[left:right+1] 和进行字典序比较的操作在最坏情况下需要 $O(N)$。因此总复杂度为 $O(N^2)$。
  • 鉴于 $N\le 100$，这个复杂度可以轻松通过。
• 空间复杂度：$O(N)$。用于存储当前找到的最优美丽子字符串。

为什么这个方法有效？

最短的美丽子字符串一定是以 '1' 开头并以 '1' 结尾的。因为如果两端有 '0'，去掉它们后 '1' 的数量不变但长度更短。滑动窗口的收缩逻辑保证了我们考察的每个 current_str 都是以 left 位置的 '1' 开头并以 right 位置的 '1' 结尾的，从而覆盖了所有潜在的最优解。