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

标签: 字符串 滑动窗口

难度: Medium

给你一个二进制字符串 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

Submission

运行时间: 26 ms

内存: 15.9 MB

class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        res=[]
        t=0
        c=0
        a=False
        for x,i in enumerate(s):
            if i=='1':
                t+=1
            while t>k:
                if s[c]=='1':
                    t-=1
                    c+=1
            while c<x and s[c]=='0':
                c+=1
            if t==k:
                res.append(s[c:x+1])
        if not res:
            return ''
        mi=len(res[0])
        for i in res:
            mi=min(mi,len(i))
        re=[]
        for i in res:
            if len(i)==mi:
                re.append(i)
        re.sort()
        return re[0]

Explain

该解法使用了一个滑动窗口的策略来找到所有包含恰好 k 个 '1' 的子字符串。首先，定义两个指针 c (窗口左边界) 和 x (窗口右边界) 来扫描整个字符串。变量 t 用于记录当前窗口中 '1' 的数量。当 t 大于 k 时，移动左边界 c 直到 t 等于 k。随后检查左边界的 '0'，若左边界是 '0' 则向右移动以找到最短的子字符串。每次当 t 等于 k 时，记录当前的子字符串。最后，在记录的所有满足条件的子字符串中找到长度最短且字典序最小的字符串返回。

时间复杂度: O(n + m log m)

空间复杂度: O(m * n)

class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        res=[]  # 存储找到的所有满足条件的子字符串
        t=0  # 当前窗口内 '1' 的数量
        c=0  # 窗口的左边界
        for x, i in enumerate(s):  # x 是当前考虑的字符的位置，i 是字符本身
            if i=='1':
                t+=1  # 如果当前字符是 '1'，增加计数
            while t>k:  # 如果 '1' 的数量超过了 k，需要移动左边界直到 '1' 的数量等于 k
                if s[c]=='1':
                    t-=1
                c+=1
            while c<x and s[c]=='0':  # 移动左边界跳过开头的 '0' 以找到最短的子字符串
                c+=1
            if t==k:  # 如果当前窗口内 '1' 的数量正好是 k，记录下来
                res.append(s[c:x+1])
        if not res:  # 如果没有找到任何满足条件的子字符串，返回空字符串
            return ''
        mi=len(res[0])
        for i in res:  # 找到最短的子字符串长度
            mi=min(mi,len(i))
        re=[]
        for i in res:  # 收集所有最短的子字符串
            if len(i)==mi:
                re.append(i)
        re.sort()  # 对所有最短的子字符串按字典序排序
        return re[0]  # 返回字典序最小的字符串

Explore

在算法中，通过维护一个计数变量 t 来记录窗口内 '1' 的数量。每当 t 大于 k，就移动窗口的左边界 c，直到 t 减少至 k。这个过程通过检查并调整左边界 c 的位置，确保每次当窗口内的 '1' 数量超过 k 时，能够通过移动窗口左边界来减少 '1' 的数量至恰好 k。这样，每次记录子字符串时，都确保了其包含的 '1' 数量恰好为 k。

在代码中，移动左边界 c 跳过 '0' 是在确认窗口内已经有 k 个 '1' 之后进行的。这一步只是为了缩短子字符串的长度，并不会改变窗口内 '1' 的数量。因此，这一步并不会导致错过任何有效的子字符串。左边界的移动只发生在 '1' 的数量已经正确匹配为 k 之后，所以不会影响窗口内 '1' 的计数。

如果子字符串的开头是 '0', 算法中已经包含了逻辑来移动左边界 c 跳过这些 '0'。这样做的目的是确保记录的子字符串长度尽可能短，同时确保字典序尽可能小。因此，这种处理会有助于找到最短且字典序最小的子字符串，而不会影响到最终的长度和字典序判断。

在找到所有满足条件的子字符串后，需要进行排序以确保可以选择出字典序最小的字符串。虽然这一步增加了额外的时间复杂度，但是通常情况下，满足条件的子字符串数量并不会非常大，因此排序的代价相对较小。此外，排序是必要的，因为只有这样才能确保结果是字典序最小的。这是一种权衡效率和正确性的实用做法。