题目描述
给你一个二进制字符串 s
和一个正整数 k
。
如果 s
的某个子字符串中 1
的个数恰好等于 k
,则称这个子字符串是一个 美丽子字符串。
令 len
等于 最短 美丽子字符串的长度。
返回长度等于 len
且字典序 最小 的美丽子字符串。如果 s
中不含美丽子字符串,则返回一个 空 字符串。
对于相同长度的两个字符串 a
和 b
,如果在 a
和 b
出现不同的第一个位置上,a
中该位置上的字符严格大于 b
中的对应字符,则认为字符串 a
字典序 大于 字符串 b
。
例如,"abcd"
的字典序大于 "abcc"
,因为两个字符串出现不同的第一个位置对应第四个字符,而 d
大于 c
。
样例
输入:s = "100011001", k = 3
输出:"11001"
解释:示例中共有 7 个美丽子字符串:
1. 子字符串 "100011001"。
2. 子字符串 "100011001"。
3. 子字符串 "100011001"。
4. 子字符串 "100011001"。
5. 子字符串 "100011001"。
6. 子字符串 "100011001"。
7. 子字符串 "100011001"。
最短美丽子字符串的长度是 5 。
长度为 5 且字典序最小的美丽子字符串是子字符串 "11001"。
输入:s = "1011", k = 2
输出:"11"
解释:示例中共有 3 个美丽子字符串:
1. 子字符串 "1011"。
2. 子字符串 "1011"。
3. 子字符串 "1011"。
最短美丽子字符串的长度是 2。
长度为 2 且字典序最小的美丽子字符串是子字符串 "11"。
输入:s = "000", k = 1
输出:""
解释:示例中不存在美丽子字符串。
限制
1 <= s.length <= 100
1 <= k <= s.length
算法
(暴力枚举) $O(n^2)$
- 如果在求最短子字符串的过程中比较字典序最小的子字符串,则时间复杂度会退化到 $O(n^3)$。
- 所以,先通过暴力枚举求出最短子字符串的长度,然后再通过滑动窗口,求出字典序最小的字符串。
时间复杂度
- 暴力枚举求出最短子字符串的长度的时间复杂度为 $O(n^2)$。
- 共有 $O(n)$ 个滑动窗口,每个窗口比较字典序最小的字符串时间复杂度为 $O(n)$。
- 故总时间复杂度为 $O(n^2)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储对比字典序的子字符串。
C++ 代码
class Solution {
public:
string shortestBeautifulSubstring(string s, int k) {
const int n = s.size();
int len = n + 1;
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = i; j < n; j++) {
if (s[j] == '1')
++cnt;
if (cnt == k) {
len = min(len, j - i + 1);
break;
}
}
}
if (len == n + 1)
return "";
int cnt = 0;
string ans;
for (int i = 0; i < n; i++) {
cnt += s[i] == '1';
if (i >= len - 1) {
if (cnt == k) {
string t = s.substr(i - len + 1, len);
if (ans == "" || ans > t)
ans = t;
}
cnt -= s[i - len + 1] == '1';
}
}
return ans;
}
};