LeetCode 解題筆記：2904. Shortest and Lexicographically Smallest Beautiful String

作者：王一哲
日期：2026年8月26日


LeetCode 題目連結：2904. Shortest and Lexicographically Smallest Beautiful String

解題想法

中等難度題。題目給一個只有 01 的字串 $s$，要找出 $s$ 之中連續的子字串而且子字串中正好有 $k$ 個 $1$，回傳符合要求的最短子字串，如果有多個長度相同且符合規則的子字串，回傳之中字典序最小者。由於題目要找的是連續子字串，很適合用滑動視窗解題。先用一個 for 迴圈更新視窗右端點 $right$ 從 $0$ 到 $n-1$，先依照 $s[right]$ 更新 $1$ 的數量 $ones$；再用一個 while 迴圈，如果 $ones > k$ 或是 $ones = k$ 且 $s[left] = '0'$，更新 $ones$、再將 $left$ 向右移一格；跑完 while 迴圈之後，如果 $ones = k$，而且子字串長度較短或長度相等但子字串字典序較小就更新答案。由於用 C 語言處理字串很麻煩，我就不寫 C 語言版本了。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.32 MB, beats 30.63%.

class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        # 長度，目前範圍中有幾個1，視窗左端點
        n, ones, left = len(s), 0, 0
        ans = "1" * (n+1)  # 答案，預設為超出上限的字串
        # 滑動視窗，移動右端點
        for right in range(n):
            # 更新範圍內 1 的數量
            if s[right] == '1': ones += 1
            # ones 大於 k 或 ones 等於 k 且 s[left] 是 0
            while ones > k or (ones == k and s[left] == '0'):
                if s[left] == '1': ones -= 1  # 更新範圍內 1 的數量
                left += 1  # 向右移1格
            # 如果 1 的數量等於 k，更新答案
            if ones == k:
                sub = s[left : right + 1]  # 子字串
                length = right - left + 1  # 子字串長度
                # 如果子字串長度較短或長度相等但子字串字典序較小，更新答案
                if length < len(ans) or (length == len(ans) and sub < ans): 
                    ans = sub
        return ans if ans != "1" * (n+1) else ""

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.94 MB, beats 37.53%.

class Solution {
public:
    string shortestBeautifulSubstring(string s, int k) {
        // 長度，目前範圍中有幾個1，視窗左端點
        int n = (int)s.size(), ones = 0, left = 0;
        string ans (n+1, '1');  // 答案，預設為超出上限的字串
        string original = ans;  // 預設的答案
        // 滑動視窗，移動右端點
        for(int right = 0; right < n; right++) {
            // 更新範圍內 1 的數量
            if (s[right] == '1') ones++;
            // ones 大於 k 或 ones 等於 k 且 s[left] 是 0
            while(ones > k || (ones == k && s[left] == '0')) {
                if (s[left] == '1') ones--;  // 更新範圍內 1 的數量
                left++;  // 向右移1格
            }
            // 如果 1 的數量等於 k，更新答案
            if (ones == k) {
                int length = right - left + 1, curr = (int)ans.size();  // 子字串長度，目前的答案長度
                string sub = s.substr(left, length);  // 子字串
                // 如果子字串長度較短或長度相等但子字串字典序較小，更新答案
                if (length < curr || (length == curr && sub < ans)) ans = sub;
            }
        }
        return (ans != original ? ans : "");
    }
};