Medium

题目描述

给你一个二进制字符串 s 和一个正整数 k。

如果 s 的一个子字符串中恰好包含 k 个 1，则称这个子字符串是美丽的。

设 len 为最短美丽子字符串的长度。

返回长度等于 len 且字典序最小的美丽子字符串。如果 s 中不存在美丽子字符串，则返回一个空字符串。

字符串 a 字典序比字符串 b 大（相同长度），当且仅在它们第一个不同的位置上 a 的字符严格大于 b 的对应字符。

  • 例如，"abcd" 字典序比 "abcc" 大，因为它们第一个不同的位置是第四个字符，d 大于 c。

示例 1:

输入：s = "100011001", k = 3
输出："11001"
解释：有 7 个美丽子字符串。最短美丽子字符串的长度为 5。
长度为 5 的字典序最小的美丽子字符串是 "11001"。

示例 2:

输入：s = "1011", k = 2
输出："11"
解释：有 3 个美丽子字符串。最短美丽子字符串的长度为 2。
长度为 2 的字典序最小的美丽子字符串是 "11"。

示例 3:

输入：s = "000", k = 1
输出：""
解释：这个例子中没有美丽子字符串。

约束：

  • 1 <= s.length <= 100
  • 1 <= k <= s.length

解题思路

解题思路

这是一个滑动窗口问题，我们需要找到最短且字典序最小的包含恰好 k 个 ‘1’ 的子字符串。

主要思路：

  1. 枚举起点法：对于每个可能的起始位置 i，找到从该位置开始的最短美丽子字符串
  2. 滑动窗口扩展：从位置 i 开始，逐步扩展窗口直到包含恰好 k 个 ‘1’
  3. 最优解更新：比较所有找到的美丽子字符串，选择最短的；如果长度相同，选择字典序最小的

具体算法：

  • 遍历每个起始位置 i
  • 从位置 i 开始，使用双指针技术扩展窗口
  • 当窗口内 ‘1’ 的个数等于 k 时，记录这个子字符串
  • 比较长度：优先选择更短的子字符串
  • 长度相同时，选择字典序更小的

优化点：

  • 提前剪枝：如果当前位置到字符串末尾的长度小于已找到的最短长度，可以直接跳出
  • 字典序比较：只有在长度相等或更短时才需要比较字典序

时间复杂度主要由枚举起点和扩展窗口决定，最坏情况下为 O(n²)。

代码实现

class Solution {
public:
    string shortestBeautifulSubstring(string s, int k) {
        int n = s.length();
        string result = "";
        int minLen = INT_MAX;
        
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') continue;  // 只从'1'开始
            
            int count = 0;
            for (int j = i; j < n; j++) {
                if (s[j] == '1') count++;
                
                if (count == k) {
                    string current = s.substr(i, j - i + 1);
                    int currentLen = j - i + 1;
                    
                    if (currentLen < minLen || 
                        (currentLen == minLen && current < result)) {
                        minLen = currentLen;
                        result = current;
                    }
                    break;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        n = len(s)
        result = ""
        min_len = float('inf')
        
        for i in range(n):
            if s[i] == '0':
                continue  # 只从'1'开始
            
            count = 0
            for j in range(i, n):
                if s[j] == '1':
                    count += 1
                
                if count == k:
                    current = s[i:j+1]
                    current_len = j - i + 1
                    
                    if current_len < min_len or (current_len == min_len and current < result):
                        min_len = current_len
                        result = current
                    break
        
        return result

public class Solution {
    public string ShortestBeautifulSubstring(string s, int k) {
        int n = s.Length;
        string result = "";
        int minLen = int.MaxValue;
        
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') continue;  // 只从'1'开始
            
            int count = 0;
            for (int j = i; j < n; j++) {
                if (s[j] == '1') count++;
                
                if (count == k) {
                    string current = s.Substring(i, j - i + 1);
                    int currentLen = j - i + 1;
                    
                    if (currentLen < minLen || 
                        (currentLen == minLen && string.Compare(current, result) < 0)) {
                        minLen = currentLen;
                        result = current;
                    }
                    break;
                }
            }
        }
        
        return result;
    }
}

var shortestBeautifulSubstring = function(s, k) {
    const n = s.length;
    let result = "";
    let minLen = Infinity;
    
    for (let i = 0; i < n; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n²) - 外层循环遍历起始位置，内层循环扩展窗口
空间复杂度O(1) - 除了结果字符串外，只使用常数级额外空间