字符串计数匹配 (Python JAVA C++ JS C)-程序员充电站

题目描述

给你一个字符串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; }