Given two strings, determine the number of times the first one appears as a subsequence in the second one. A subsequence is created by eliminating any number of characters from a string (possibly 0) without changing the order of the characters retained.
Example
s1 = "ABC"
s2 = "ABCBABC"The string s1 appears 5 times as a subsequence in s2 at 1-indexed positions (1,2,3), (1,2,7), (1,4,7), (1,6,7), (5,6,7). Answer: 5.
Constraints
- length of
s1= 3 - 1 ≤ length of
s2≤ 5·10⁵ - both strings consist of uppercase English letters A-Z.
解法
一维 DP。dp[i] 表示 s1 前 i 个字符作为 s2 已扫描前缀子序列的方案数。遍历 s2 的每个字符 c，对满足 s1[i-1] == c 的位置更新 dp[i] += dp[i-1]；i 倒序遍历保证每个 s2 字符只用一次。时间 O(n · m)，空间 O(n)。
def get_subsequence_count(s1, s2):
n = len(s1)
if n > len(s2):
return 0
dp = [0] * (n + 1)
dp[0] = 1
for c in s2:
for i in range(n, 0, -1):
if s1[i-1] == c:
dp[i] += dp[i-1]
return dp[n]class Solution {
static long getSubsequenceCount(String s1, String s2) {
int n = s1.length(), m = s2.length();
if (n > m) return 0;
long[] dp = new long[n + 1];
dp[0] = 1;
for (int j = 0; j < m; j++) {
char c = s2.charAt(j);
for (int i = n; i >= 1; i--)
if (s1.charAt(i - 1) == c) dp[i] += dp[i - 1];
}
return dp[n];
}
}long long getSubsequenceCount(string s1, string s2) {
int n = s1.size(), m = s2.size();
if (n > m) return 0;
vector<long long> dp(n + 1, 0);
dp[0] = 1;
for (int j = 0; j < m; j++) {
char c = s2[j];
for (int i = n; i >= 1; i--)
if (s1[i - 1] == c) dp[i] += dp[i - 1];
}
return dp[n];
}Given n machine learning models, each with cost cost[i] and a binary string featureAvailability[i] of length 2 indicating support for two features A and B:
"00"neither feature"01"feature A only"10"feature B only"11"both features
A set of models is k-capable if the count of models supporting feature A is ≥ k AND the count of models supporting feature B is ≥ k. For each k from 1 to n, return the minimum total cost of a k-capable set; if no such set exists, return -1 at that position.
Example
n = 6
cost = [3, 6, 9, 1, 2, 5]
featureAvailability = ["10", "01", "11", "01", "11", "10"]Answer: [2, 6, 15, 26, -1, -1].
Constraints
- 1 ≤ n ≤ 10³
- 1 ≤ cost[i] ≤ 10⁴
featureAvailability[i]is a binary string of length 2.
解法
按类型分桶：T11(同时支持 A 和 B)、T10(只支持 B)、T01(只支持 A)，忽略 T00。每桶按 cost 升序排序并构造前缀和 S11、S10、S01。目标 k：从 T11 选 j 个(同时贡献 A 和 B 各 j)，再分别从 T01 和 T10 各补 k-j 个(j < k 时)。固定 j 的最小代价：
cost(k, j) = S11[j] + S01[max(k-j,0)] + S10[max(k-j,0)]要求 j ≤ |T11|、k-j ≤ |T01|、k-j ≤ |T10|。在合法区间 [max(0, k-|T01|, k-|T10|), min(k, |T11|)] 内取最小。时间 O(n²)，空间 O(n)。
def get_minimum_cost(cost, feature_availability):
t11, t10, t01 = [], [], []
for c, s in zip(cost, feature_availability):
if s == "11":
t11.append(c)
elif s == "10":
t10.append(c)
elif s == "01":
t01.append(c)
t11.sort(); t10.sort(); t01.sort()
def prefix(a):
p = [0] * (len(a) + 1)
for i, x in enumerate(a):
p[i+1] = p[i] + x
return p
P11, P10, P01 = prefix(t11), prefix(t10), prefix(t01)
n = len(cost)
ans = []
for k in range(1, n + 1):
best = None
jmin = max(0, k - len(t01), k - len(t10))
jmax = min(k, len(t11))
for j in range(jmin, jmax + 1):
r = k - j
c = P11[j] + P01[r] + P10[r]
if best is None or c < best:
best = c
ans.append(best if best is not None else -1)
return ansclass Solution {
static int[] getMinimumCost(int[] cost, String[] feature) {
int n = cost.length;
List<Integer> t11 = new ArrayList<>(), t10 = new ArrayList<>(), t01 = new ArrayList<>();
for (int i = 0; i < n; i++) {
String s = feature[i];
if (s.equals("11")) t11.add(cost[i]);
else if (s.equals("10")) t10.add(cost[i]);
else if (s.equals("01")) t01.add(cost[i]);
}
Collections.sort(t11); Collections.sort(t10); Collections.sort(t01);
long[] P11 = prefix(t11), P10 = prefix(t10), P01 = prefix(t01);
int[] ans = new int[n];
for (int k = 1; k <= n; k++) {
long best = Long.MAX_VALUE;
int jmin = Math.max(0, Math.max(k - t01.size(), k - t10.size()));
int jmax = Math.min(k, t11.size());
for (int j = jmin; j <= jmax; j++) {
int r = k - j;
long c = P11[j] + P01[r] + P10[r];
if (c < best) best = c;
}
ans[k - 1] = best == Long.MAX_VALUE ? -1 : (int) best;
}
return ans;
}
static long[] prefix(List<Integer> a) {
long[] p = new long[a.size() + 1];
for (int i = 0; i < a.size(); i++) p[i + 1] = p[i] + a.get(i);
return p;
}
}vector<int> getMinimumCost(vector<int>& cost, vector<string>& feature) {
int n = cost.size();
vector<int> t11, t10, t01;
for (int i = 0; i < n; i++) {
if (feature[i] == "11") t11.push_back(cost[i]);
else if (feature[i] == "10") t10.push_back(cost[i]);
else if (feature[i] == "01") t01.push_back(cost[i]);
}
sort(t11.begin(), t11.end());
sort(t10.begin(), t10.end());
sort(t01.begin(), t01.end());
auto prefix = [](vector<int>& a) {
vector<long long> p(a.size() + 1, 0);
for (size_t i = 0; i < a.size(); i++) p[i + 1] = p[i] + a[i];
return p;
};
auto P11 = prefix(t11), P10 = prefix(t10), P01 = prefix(t01);
vector<int> ans(n);
for (int k = 1; k <= n; k++) {
long long best = LLONG_MAX;
int jmin = max({0, k - (int)t01.size(), k - (int)t10.size()});
int jmax = min(k, (int)t11.size());
for (int j = jmin; j <= jmax; j++) {
int r = k - j;
long long c = P11[j] + P01[r] + P10[r];
if (c < best) best = c;
}
ans[k - 1] = best == LLONG_MAX ? -1 : (int) best;
}
return ans;
}Given an array of integers, for each element determine whether that element occurs earlier in the array and whether it occurs later in the array. Create two strings of binary digits. In the first string, each character is a 1 if the value at that index also occurs earlier in the array, or 0 if not. In the second string, each character is a 1 if the value at that index occurs later in the array, or 0 if not. Return an array of two strings where the first string is related to lower indices and the second to higher.
Function Description
Complete the function bitPattern in the editor below.
bitPattern has the following parameter(s):
int num[n]: an array of integers Returnsstring[2]: an array of 2 strings as described Input Format for Custom Testing Input from stdin will be processed as follows and passed to the function. The first line contains an integer n, the size of the array num. Each of the next n lines contains an integer num[i].
Constraints
1 ≤ n ≤ 10⁴⁰ ≤ num[i] ≤ 10⁴
解法
两遍扫描：从左到右用 HashSet 标记已出现过的值，构造第一个字符串(出现过为 '1')；从右到左同样构造第二个。复杂度 O(n)。
def bitPattern(num):
n = len(num)
seen = set()
left = [''] * n
for i in range(n):
left[i] = '1' if num[i] in seen else '0'
seen.add(num[i])
seen.clear()
right = [''] * n
for i in range(n - 1, -1, -1):
right[i] = '1' if num[i] in seen else '0'
seen.add(num[i])
return [''.join(left), ''.join(right)]class Solution {
public String[] bitPattern(int[] num) {
int n = num.length;
java.util.HashSet<Integer> seen = new java.util.HashSet<>();
char[] left = new char[n], right = new char[n];
for (int i = 0; i < n; i++) {
left[i] = seen.contains(num[i]) ? '1' : '0';
seen.add(num[i]);
}
seen.clear();
for (int i = n - 1; i >= 0; i--) {
right[i] = seen.contains(num[i]) ? '1' : '0';
seen.add(num[i]);
}
return new String[]{new String(left), new String(right)};
}
}class Solution {
public:
vector<string> bitPattern(vector<int>& num) {
int n = num.size();
unordered_set<int> seen;
string left(n, '0'), right(n, '0');
for (int i = 0; i < n; ++i) {
if (seen.count(num[i])) left[i] = '1';
seen.insert(num[i]);
}
seen.clear();
for (int i = n - 1; i >= 0; --i) {
if (seen.count(num[i])) right[i] = '1';
seen.insert(num[i]);
}
return {left, right};
}
};