【Leetcode Daily】2904最短且字典序最小的美丽子字符串

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个由 0 和 1 组成的字符串，找出其中子字符串的最短长度，该子字符串要满足条件：1. 其中恰好有 k 个 1；2. 字典序在相同长度的子字符串中最小；

思路分享

• 简单不定长滑动窗口（【Leetcode Daily】3090每个字符最多出现两次的最长字符串）的应用，思路上不用多说，主要讲讲从灵茶山艾府的题解中吸取到的经验。

  https://leetcode.cn/problems/shortest-and-lexicographically-smallest-beautiful-string/solutions/2483144/mei-ju-pythonjavacgo-by-endlesscheng-5th8/

• 一个是ranges::系列的学习，除了之前排序的 range::sort，这次还有 ranges::count，ranges::count(str, ‘1’)就会统计字符串 str 中字符 1 的个数。

• 还有就是 move 函数，比如 s = move(str); 可以快速地把字符串 str 的内容放到 s 中，在追求效率的算法竞赛中挺有用的。

代码解答（强烈建议自行解答后再看）

• 参考解法

class Solution {
public:
    string shortestBeautifulSubstring(string s, int k) {
        if (ranges::count(s, '1') < k) return "";
        string ans = s;
        int right = 0;
        int one_count = 0;
        int n = s.size();
        for (int left = 0; left < n; left++) {
            while(one_count < k && right < n) {
                if (s[right++]=='1') one_count++;
            }
            if (one_count == k && right <= n) {
                //cout << left << " " << right << endl;
                string tmp(s.begin()+left, s.begin()+right);
                //cout << tmp << endl;
                if (tmp.size() < ans.size() || tmp.size() == ans.size() && tmp < ans) {
                    ans = move(tmp);
                }
            }
            if (s[left]=='1') one_count--;
        }
        return ans;
    }
};