)
题目描述
给你一个字符串str和整数k，返回满足以下条件的所有子字符串个数：
- 恰好包含k个字母。
- 数字0-9各出现至少一次。
输入描述
- 第一行字符串str(1≤ length ≤ 100000),仅包含数字和小写字母
- 第二行为整数k(0 ≤ k ≤100000 )
输出描述
输出一个整数，表示满足所有条件的子字符串的个数。
子字符串是字符串中连续的非空字符序列
示例1
输入
a0123456789aa 1输出
2
问题分析
题目要求统计满足以下条件的子字符串个数：
- 子字符串恰好包含
k个字母（大小写不敏感，题目中均为小写字母）。 - 子字符串中数字
0-9各出现至少一次。
解决思路
- 滑动窗口：使用滑动窗口技术高效遍历所有可能的子字符串。
- 字母计数：维护窗口内字母的数量，确保恰好为
k。 - 数字覆盖：确保窗口内包含所有数字
0-9至少一次。 - 优化检查：在满足字母数量时检查数字覆盖情况。
算法步骤
- 初始化左右指针
left和right，表示窗口的左右边界。 - 维护两个哈希表或数组：
letterCount统计字母数量，digitCount统计数字出现情况。 - 移动右指针扩展窗口，更新计数。
- 当字母数量等于
k时，检查数字是否覆盖0-9。 - 移动左指针收缩窗口，确保字母数量不超过
k。
代码实现
C++ 实现
#include <iostream> #include <string> #include <unordered_map> using namespace std; int countSubstrings(const string &str, int k) { int n = str.size(); int res = 0; int left = 0; unordered_map<char, int> letterCount; unordered_map<char, int> digitCount; int requiredDigits = 10; for (int right = 0; right < n; ++right) { char c = str[right]; if (isdigit(c)) { digitCount[c]++; } else { letterCount[c]++; } while (letterCount.size() > k || (letterCount.size() == k && digitCount.size() < requiredDigits)) { char leftChar = str[left]; if (isdigit(leftChar)) { digitCount[leftChar]--; if (digitCount[leftChar] == 0) { digitCount.erase(leftChar); } } else { letterCount[leftChar]--; if (letterCount[leftChar] == 0) { letterCount.erase(leftChar); } } left++; } if (letterCount.size() == k && digitCount.size() == requiredDigits) { res++; } } return res; } int main() { string str; int k; cin >> str >> k; cout << countSubstrings(str, k) << endl; return 0; }Python 实现
def count_substrings(s, k): n = len(s) res = 0 left = 0 letter_count = {} digit_count = {} required_digits = 10 for right in range(n): c = s[right] if c.isdigit(): digit_count[c] = digit_count.get(c, 0) + 1 else: letter_count[c] = letter_count.get(c, 0) + 1 while len(letter_count) > k or (len(letter_count) == k and len(digit_count) < required_digits): left_char = s[left] if left_char.isdigit(): digit_count[left_char] -= 1 if digit_count[left_char] == 0: digit_count.pop(left_char) else: letter_count[left_char] -= 1 if letter_count[left_char] == 0: letter_count.pop(left_char) left += 1 if len(letter_count) == k and len(digit_count) == required_digits: res += 1 return res s = input().strip() k = int(input()) print(count_substrings(s, k))Java 实现
import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str = scanner.nextLine(); int k = scanner.nextInt(); System.out.println(countSubstrings(str, k)); } public static int countSubstrings(String str, int k) { int n = str.length(); int res = 0; int left = 0; HashMap<Character, Integer> letterCount = new HashMap<>(); HashMap<Character, Integer> digitCount = new HashMap<>(); int requiredDigits = 10; for (int right = 0; right < n; right++) { char c = str.charAt(right); if (Character.isDigit(c)) { digitCount.put(c, digitCount.getOrDefault(c, 0) + 1); } else { letterCount.put(c, letterCount.getOrDefault(c, 0) + 1); } while (letterCount.size() > k || (letterCount.size() == k && digitCount.size() < requiredDigits)) { char leftChar = str.charAt(left); if (Character.isDigit(leftChar)) { digitCount.put(leftChar, digitCount.get(leftChar) - 1); if (digitCount.get(leftChar) == 0) { digitCount.remove(leftChar); } } else { letterCount.put(leftChar, letterCount.get(leftChar) - 1); if (letterCount.get(leftChar) == 0) { letterCount.remove(leftChar); } } left++; } if (letterCount.size() == k && digitCount.size() == requiredDigits) { res++; } } return res; } }JavaScript 实现
function countSubstrings(str, k) { let n = str.length; let res = 0; let left = 0; let letterCount = new Map(); let digitCount = new Map(); const requiredDigits = 10; for (let right = 0; right < n; right++) { const c = str[right]; if (/\d/.test(c)) { digitCount.set(c, (digitCount.get(c) || 0) + 1); } else { letterCount.set(c, (letterCount.get(c) || 0) + 1); } while (letterCount.size > k || (letterCount.size === k && digitCount.size < requiredDigits)) { const leftChar = str[left]; if (/\d/.test(leftChar)) { digitCount.set(leftChar, digitCount.get(leftChar) - 1); if (digitCount.get(leftChar) === 0) { digitCount.delete(leftChar); } } else { letterCount.set(leftChar, letterCount.get(leftChar) - 1); if (letterCount.get(leftChar) === 0) { letterCount.delete(leftChar); } } left++; } if (letterCount.size === k && digitCount.size === requiredDigits) { res++; } } return res; } const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); let input = []; rl.on('line', (line) => { input.push(line); if (input.length === 2) { const str = input[0]; const k = parseInt(input[1]); console.log(countSubstrings(str, k)); rl.close(); } });C 实现
#include <stdio.h> #include <string.h> #include <ctype.h> #define MAX_CHAR 128 int countSubstrings(const char *str, int k) { int n = strlen(str); int res = 0; int left = 0; int letterCount[MAX_CHAR] = {0}; int digitCount[MAX_CHAR] = {0}; int uniqueLetters = 0; int uniqueDigits = 0; int requiredDigits = 10; for (int right = 0; right < n; ++right) { char c = str[right]; if (isdigit(c)) { if (digitCount[c] == 0) { uniqueDigits++; } digitCount[c]++; } else { if (letterCount[c] == 0) { uniqueLetters++; } letterCount[c]++; } while (uniqueLetters > k || (uniqueLetters == k && uniqueDigits < requiredDigits)) { char leftChar = str[left]; if (isdigit(leftChar)) { digitCount[leftChar]--; if (digitCount[leftChar] == 0) { uniqueDigits--; } } else { letterCount[leftChar]--; if (letterCount[leftChar] == 0) { uniqueLetters--; } } left++; } if (uniqueLetters == k && uniqueDigits == requiredDigits) { res++; } } return res; } int main() { char str[100001]; int k; scanf("%s %d", str, &k); printf("%d\n", countSubstrings(str, k)); return 0; }代码说明
- 滑动窗口：通过左右指针动态调整窗口大小。
- 哈希表/数组：用于统计字母和数字的出现次数。
- 条件检查：确保字母数量为
k且数字覆盖0-9。 - 时间复杂度：O(n)，每个字符最多被访问两次（左右指针各一次）。
- 空间复杂度：O(1)，使用固定大小的数组或哈希表。
