A subsequence of a given string is generated by deleting zero or more characters from a string, then concatenating the remaining characters. A good subsequence is one where the frequency of each character is the same. Given a string that consists of n Latin letters, determine how many good subsequences it contains. Since the answer can be quite large, compute its modulo (10⁹ + 7).
Note: An empty subsequence is not a good subsequence.
Function Description
Complete the function countGoodSubsequences in the editor below.
countGoodSubsequences has the following parameter(s):
- string word: a string that consists of only lowercase Latin letters
Returns
int: the number of good subsequences modulo (10⁹ + 7)
Example 1
Input:
word = "abca"Output:
12Explanation: A total of 15 non-empty subsequences can be formed from words: "a", "a", "aa", "ab", "aba", "abc", "abca", "ac", "aca", "b", "ba", "bc", "bca", "c", and "ca". The only subsequences that are not good are "aba," "aca," and "abca" as the frequency of character "a" is 2, and every other character is 1. The total number of good subsequences = 15 - 3 = 12 and answer to the above example = 12 modulo (10⁹+7) = 12.
Example 2
Input:
word = "abcd"Output:
15Explanation: All of the non-empty subsequences are good subsequences. They are "a", "ab", "abc", "abcd", "abd", "ac", "acd", "ad", "b", "bc", "bcd", "bd", "c", "cd", and "d".
解法
统计每个字符出现次数 cnt[c]。枚举"每个字符出现 k 次"(k 从 1 到 max(cnt))，对每个 k 把所有 cnt[c] ≥ k 的字符各选 k 个的方案数相乘累加，即 ∏ C(cnt[c], k) 求和。预处理阶乘逆元，时间 O(26 · max_cnt + n)。
def countGoodSubsequences(word: str) -> int:
MOD = 10**9 + 7
n = len(word)
cnt = [0] * 26
for ch in word:
cnt[ord(ch) - 97] += 1
fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i % MOD
inv_fact = [1] * (n + 1)
inv_fact[n] = pow(fact[n], MOD - 2, MOD)
for i in range(n - 1, -1, -1):
inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
def comb(a, b):
if b < 0 or b > a:
return 0
return fact[a] * inv_fact[b] % MOD * inv_fact[a - b] % MOD
ans = 0
max_cnt = max(cnt)
for k in range(1, max_cnt + 1):
prod = 1
for c in cnt:
if c >= k:
prod = prod * (comb(c, k) + 1) % MOD
# prod 包含"每种字符可选 k 个或不选"，减去全不选的 1 种
ans = (ans + prod - 1) % MOD
return ansclass Solution {
static final int MOD = 1_000_000_007;
long[] fact, invFact;
int countGoodSubsequences(String word) {
int n = word.length();
int[] cnt = new int[26];
for (char ch : word.toCharArray()) cnt[ch - 'a']++;
fact = new long[n + 1];
invFact = new long[n + 1];
fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
invFact[n] = modPow(fact[n], MOD - 2);
for (int i = n - 1; i >= 0; i--) invFact[i] = invFact[i + 1] * (i + 1) % MOD;
int maxCnt = 0;
for (int c : cnt) maxCnt = Math.max(maxCnt, c);
long ans = 0;
for (int k = 1; k <= maxCnt; k++) {
long prod = 1;
for (int c : cnt) {
if (c >= k) prod = prod * (comb(c, k) + 1) % MOD;
}
ans = (ans + prod - 1 + MOD) % MOD;
}
return (int) ans;
}
long comb(int a, int b) {
if (b < 0 || b > a) return 0;
return fact[a] * invFact[b] % MOD * invFact[a - b] % MOD;
}
long modPow(long b, long e) {
long r = 1;
b %= MOD;
while (e > 0) { if ((e & 1) == 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; }
return r;
}
}class Solution {
public:
static const int MOD = 1'000'000'007;
vector<long long> fact, invFact;
long long modPow(long long b, long long e) {
long long r = 1; b %= MOD;
while (e) { if (e & 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; }
return r;
}
long long comb(int a, int b) {
if (b < 0 || b > a) return 0;
return fact[a] * invFact[b] % MOD * invFact[a - b] % MOD;
}
int countGoodSubsequences(string word) {
int n = word.size();
vector<int> cnt(26, 0);
for (char ch : word) cnt[ch - 'a']++;
fact.assign(n + 1, 1);
invFact.assign(n + 1, 1);
for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
invFact[n] = modPow(fact[n], MOD - 2);
for (int i = n - 1; i >= 0; i--) invFact[i] = invFact[i + 1] * (i + 1) % MOD;
int maxCnt = *max_element(cnt.begin(), cnt.end());
long long ans = 0;
for (int k = 1; k <= maxCnt; k++) {
long long prod = 1;
for (int c : cnt) if (c >= k) prod = prod * (comb(c, k) + 1) % MOD;
ans = (ans + prod - 1 + MOD) % MOD;
}
return (int) ans;
}
};An employee has to work exactly as many hours as they are told to each week, scheduling no more than a given daily maximum number of hours. On some days, the hours worked will be given. The employee gets to choose the remainder of their schedule, within the given limits.
A completed schedule consists of exactly 7 digits in the range 0 to 8 that represent each day's work hours. A pattern string similar to the schedule is given, but the scheduled hours are marked by a question mark, ?, (ascii 63 decimal). Given a maximum number of hours that can be worked in a day, replace the question marks with digits so the scheduled hours is exactly the total hours that must be worked in a week.
Determine all possible work schedules that meet the requirements and return them as a list of strings, sorted ascending.
Function Description
Complete the function findSchedules in the editor.
findSchedules has the following parameter(s):
-
int work_hours: the hours that must be worked in the week
-
int day_hours: the maximum hours that may be worked in a day
-
String pattern: the partially completed schedule ReturnsString arr[]: represents all possible valid schedules (must be ordered lexicographically ascending)
Constraints
- 1 ≤ work_hours ≤ 56
- 1 ≤ day_hours ≤ 8
- | pattern | = 7
- Each character of pattern ∈ {0, 1, ..., 8}
- There is at least one correct schedule.
Example 1
Input:
work_hours = 24
day_hours = 4
pattern = "08??840"Output:
["0804840", "0813840", "0822840", "0831840", "0840840"]Explanation: There are 2 days on which they must work 24-20=4 more hours for the week. All of the possible schedules are listed below: 0804840 0813840 0822840 0831840 0840840
Example 2
Input:
work_hours = 56
day_hours = 8
pattern = "???8???"Output:
["8888888"]Explanation: There is only one way to work 56 hours in 7 days of 8 hours.
Example 3
Input:
work_hours = 3
day_hours = 8
pattern = "??2??00"Output:
["0020100", "0021000", "0120000", "1020000"]Explanation: work_hours = 3 day_hours = 2 pattern = '??2??00' They only need to schedule 1 more hour for the week, and it can be on any one of the days in question.
解法
回溯枚举每个 ? 填 0..day_hours，剪枝：剩余 ? 个数乘 day_hours 必须 ≥ 还差的小时数，已填总和不能超 work_hours。按位置从左到右填，自然得到字典序升序结果。时间 O((day_hours+1)^q)，q ≤ 7。
from typing import List
def findSchedules(work_hours: int, day_hours: int, pattern: str) -> List[str]:
chars = list(pattern)
q_idx = [i for i, c in enumerate(chars) if c == '?']
fixed_sum = sum(int(c) for c in chars if c != '?')
need = work_hours - fixed_sum
res = []
def dfs(i: int, remain: int):
if i == len(q_idx):
if remain == 0:
res.append(''.join(chars))
return
left = len(q_idx) - i
# 剪枝：剩余位置最多能填 left * day_hours
if remain < 0 or remain > left * day_hours:
return
for d in range(0, day_hours + 1):
chars[q_idx[i]] = str(d)
dfs(i + 1, remain - d)
chars[q_idx[i]] = '?'
dfs(0, need)
return resimport java.util.*;
class Solution {
List<String> res;
char[] chars;
int[] qIdx;
int dayHours;
List<String> findSchedules(int work_hours, int day_hours, String pattern) {
chars = pattern.toCharArray();
dayHours = day_hours;
List<Integer> qs = new ArrayList<>();
int fixed = 0;
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '?') qs.add(i);
else fixed += chars[i] - '0';
}
qIdx = qs.stream().mapToInt(Integer::intValue).toArray();
res = new ArrayList<>();
dfs(0, work_hours - fixed);
return res;
}
void dfs(int i, int remain) {
if (i == qIdx.length) {
if (remain == 0) res.add(new String(chars));
return;
}
int left = qIdx.length - i;
if (remain < 0 || remain > (long) left * dayHours) return;
for (int d = 0; d <= dayHours; d++) {
chars[qIdx[i]] = (char) ('0' + d);
dfs(i + 1, remain - d);
}
chars[qIdx[i]] = '?';
}
}class Solution {
public:
vector<string> res;
string chars;
vector<int> qIdx;
int dayHours;
vector<string> findSchedules(int work_hours, int day_hours, string pattern) {
chars = pattern;
dayHours = day_hours;
int fixed = 0;
for (int i = 0; i < (int) chars.size(); i++) {
if (chars[i] == '?') qIdx.push_back(i);
else fixed += chars[i] - '0';
}
dfs(0, work_hours - fixed);
return res;
}
void dfs(int i, int remain) {
if (i == (int) qIdx.size()) {
if (remain == 0) res.push_back(chars);
return;
}
int left = (int) qIdx.size() - i;
if (remain < 0 || remain > left * dayHours) return;
for (int d = 0; d <= dayHours; d++) {
chars[qIdx[i]] = (char) ('0' + d);
dfs(i + 1, remain - d);
}
chars[qIdx[i]] = '?';
}
};You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].
The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.
Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.
Constraints
1 ≤ points.length ≤ 1000-10⁶ ≤ xi, yi ≤ 10⁶- All pairs
(xi, yi)are distinct.
Example 1
Input:
points = [[0,0],[2,2],[3,10],[5,2],[7,0]]Output:
20Explanation: We can connect the points as shown above to get the minimum cost of 20. Notice that there is a unique path between every pair of points.
Example 2
Input:
points = [[3,12],[-2,5],[-4,1]]Output:
18Explanation: The points can be connected in various ways to get the minimum cost of 18.
解法
完全图 + 曼哈顿距离的最小生成树。点数较小时直接 Prim(稠密图 O(n²))：维护每个未加入点到已选集合的最小距离 minDist，每轮挑最小值加入并松弛邻接距离。
from typing import List
def minCostConnectPoints(points: List[List[int]]) -> int:
n = len(points)
if n <= 1:
return 0
INF = float('inf')
min_dist = [INF] * n
min_dist[0] = 0
in_mst = [False] * n
total = 0
for _ in range(n):
u = -1
best = INF
for v in range(n):
if not in_mst[v] and min_dist[v] < best:
best = min_dist[v]
u = v
in_mst[u] = True
total += best
xu, yu = points[u]
for v in range(n):
if not in_mst[v]:
d = abs(xu - points[v][0]) + abs(yu - points[v][1])
if d < min_dist[v]:
min_dist[v] = d
return totalclass Solution {
int minCostConnectPoints(int[][] points) {
int n = points.length;
if (n <= 1) return 0;
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[0] = 0;
boolean[] inMst = new boolean[n];
int total = 0;
for (int k = 0; k < n; k++) {
int u = -1, best = Integer.MAX_VALUE;
for (int v = 0; v < n; v++) {
if (!inMst[v] && minDist[v] < best) {
best = minDist[v];
u = v;
}
}
inMst[u] = true;
total += best;
for (int v = 0; v < n; v++) {
if (!inMst[v]) {
int d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
if (d < minDist[v]) minDist[v] = d;
}
}
}
return total;
}
}class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size();
if (n <= 1) return 0;
vector<int> minDist(n, INT_MAX);
vector<bool> inMst(n, false);
minDist[0] = 0;
int total = 0;
for (int k = 0; k < n; k++) {
int u = -1, best = INT_MAX;
for (int v = 0; v < n; v++) {
if (!inMst[v] && minDist[v] < best) {
best = minDist[v];
u = v;
}
}
inMst[u] = true;
total += best;
for (int v = 0; v < n; v++) {
if (!inMst[v]) {
int d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1]);
if (d < minDist[v]) minDist[v] = d;
}
}
}
return total;
}
};