2904.最短且字典序最小的美丽子字符串：滑动窗口

【LetMeFly】2904.最短且字典序最小的美丽子字符串：滑动窗口

力扣题目链接：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

解题方法：滑动窗口

左右两个指针$l$和$r$代表“窗口”，每次右指针右移一位，若不满足如下条件则左指针右移：

1. 窗口中1的个数大于$k$
2. 窗口中1的个数等于$k$且左指针指向的字符为0

若左指针移动结束后窗口中1的个数等于$k$，则可能更新答案字符串。怎么判断是否更新呢？当满足以下任一条件时更新：

1. 答案字符串为空
2. 答案字符串比当前窗口字符串长
3. 答案字符串与前窗口字符串长等长但是字典序更大

以上。

• 时间复杂度$O(len(s)\times k)$
• 空间复杂度$O(k)$

AC代码

C++

/*
 * @LastEditTime: 2026-08-26 14:16:35
 */
class Solution {
private:
    void update(string& ans, string& s, int l, int r) {
        int len = r - l + 1;
        std::string_view cur(s.data() + l, len);
        if (ans.empty() || len < ans.size() || len == ans.size() && cur < ans) {
            ans = cur;
        }
    }
public:
    string shortestBeautifulSubstring(string& s, int k) {
        string ans;
        for (int l = 0, r = 0, cnt = 0, n = s.size(); r < n; r++) {
            cnt += s[r] == '1';
            while (cnt > k) {
                cnt -= s[l++] == '1';
            }
            if (cnt == k) {
                while (s[l] == '0') {  // do not forget!
                    l++;
                }
                update(ans, s, l, r);
            }
        }
        return ans;
    }
};

• 执行用时分布 0 ms 击败 100.00%
• 消耗内存分布 8.32 MB 击败 98.88%

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源