class Solution {
public:
string shortestBeautifulSubstring(string s, int k) {
}
};
2904. 最短且字典序最小的美丽子字符串
给你一个二进制字符串 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 <= 1001 <= k <= s.length原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-10-16 20:51:13
func shortestBeautifulSubstring(s string, k int) string {
if strings.Count(s, "1") < k {
return ""
}
ans := s
cnt1 := 0
left := 0
for right, b := range s {
cnt1 += int(b & 1)
for cnt1 > k || s[left] == '0' {
cnt1 -= int(s[left] & 1)
left++
}
if cnt1 == k {
t := s[left : right+1]
if len(t) < len(ans) || len(t) == len(ans) && t < ans {
ans = t
}
}
}
return ans
}
func shortestBeautifulSubstring2(s string, k int) string {
// 1 的个数不足 k
if strings.Count(s, "1") < k {
return ""
}
// 否则一定有解
for size := k; ; size++ {
ans := ""
for i := size; i <= len(s); i++ {
t := s[i-size : i]
if (ans == "" || t < ans) && strings.Count(t, "1") == k {
ans = t
}
}
if ans != "" {
return ans
}
}
}
java 解法, 执行用时: 9 ms, 内存消耗: 43 MB, 提交时间: 2023-10-16 20:50:48
class Solution {
public String shortestBeautifulSubstring(String s, int k) {
// 1 的个数不足 k
if (s.replace("0", "").length() < k) {
return "";
}
// 否则一定有解
for (int size = k; ; size++) {
String ans = "";
for (int i = size; i <= s.length(); i++) {
String t = s.substring(i - size, i);
if ((ans.isEmpty() || t.compareTo(ans) < 0) && t.replace("0", "").length() == k) {
ans = t;
}
}
if (!ans.isEmpty()) {
return ans;
}
}
}
// 滑动窗口
public String shortestBeautifulSubstring2(String S, int k) {
if (S.replace("0", "").length() < k) {
return "";
}
char[] s = S.toCharArray();
String ans = S;
int cnt1 = 0, left = 0;
for (int right = 0; right < s.length; right++) {
cnt1 += s[right] - '0';
while (cnt1 > k || s[left] == '0') {
cnt1 -= s[left++] - '0';
}
if (cnt1 == k) {
String t = S.substring(left, right + 1);
if (t.length() < ans.length() || t.length() == ans.length() && t.compareTo(ans) < 0) {
ans = t;
}
}
}
return ans;
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.5 MB, 提交时间: 2023-10-16 20:49:44
class Solution {
public:
// 滑动窗口
string shortestBeautifulSubstring(string s, int k) {
if (count(s.begin(), s.end(), '1') < k) {
return "";
}
string ans = s;
int cnt1 = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
cnt1 += s[right] - '0';
while (cnt1 > k || s[left] == '0') {
cnt1 -= s[left++] - '0';
}
if (cnt1 == k) {
string t = s.substr(left, right - left + 1);
if (t.length() < ans.length() || t.length() == ans.length() && t < ans) {
ans = move(t);
}
}
}
return ans;
}
// 枚举
string shortestBeautifulSubstring2(string s, int k) {
// 1 的个数不足 k
if (count(s.begin(), s.end(), '1') < k) {
return "";
}
// 否则一定有解
for (int size = k;; size++) {
string ans = "";
for (int i = size; i <= s.length(); i++) {
string t = s.substr(i - size, size);
if ((ans == "" || t < ans) && count(t.begin(), t.end(), '1') == k) {
ans = t;
}
}
if (!ans.empty()) {
return ans;
}
}
}
};
python3 解法, 执行用时: 56 ms, 内存消耗: 16 MB, 提交时间: 2023-10-16 20:49:08
class Solution:
# 枚举
def shortestBeautifulSubstring(self, s: str, k: int) -> str:
# 1 的个数不足 k
if s.count('1') < k:
return ''
# 否则一定有解
for size in count(k): # 从 k 开始枚举
ans = ''
for i in range(size, len(s) + 1):
t = s[i - size: i]
if (ans == '' or t < ans) and t.count('1') == k:
ans = t
if ans: return ans
# 滑动窗口
def shortestBeautifulSubstring2(self, s: str, k: int) -> str:
if s.count('1') < k:
return ''
ans = s
cnt1 = left = 0
for right, c in enumerate(s):
cnt1 += int(c)
while cnt1 > k or s[left] == '0':
cnt1 -= int(s[left])
left += 1
if cnt1 == k:
t = s[left: right + 1]
if len(t) < len(ans) or len(t) == len(ans) and t < ans:
ans = t
return ans