BNY Mellon

— / 3已做

01Calculate String Transformations Length

For a string word of length n consisting of lowercase English characters, it can be transformed as follows. For each character of the string:

If the character is 'z', it is replaced by "ab".
Otherwise, it is replaced by its next higher character, for example, 'a' is replaced by 'b', 'b' by 'c' ... and 'y' by 'z'. Thus, if the initial string is "azbk" it is "babcl" after 1 transformation. As a fun trivia, HackerRank publishes a puzzle for all its employees each week. The goal for this week is to find the length of the resultant string after exactly t transformations are performed as described above. Since the answer can be large, find the answer taking modulo (10⁹ + 7).

Example 1

Input:

word = "abczy"
t = 2

Output:

TO-DO

Explanation: Consider word = "abczy" and the number of transformations t = 2. In the 1st transformation, the characters are transformed as follows:

a → b
b → c
c → d
z → ab
y → z Resulting string: "bcdabz" In the 2nd transformation:
b → c
c → d
d → e
a → b
b → c Resulting string: "cdedbc"

考虑单个字符 c 经 t 步变换后的长度 f(c, t)。递推：'z' → 'a' + 'b'(一步后变成两个字符 a 和 b，长度 2)；其它 c → next(c)(长度 1)。设 L[c][t] 为字符 c 经 t 步后产生的字符串长度，状态可用每字母分别滚动；或观察：cnt[i][t] = "经过 t 步后第 i 个字母在结果中的个数"，转移：cnt[i][t] = cnt[i-1][t-1](i ≠ 'a','b')，cnt[0][t] = cnt[25][t-1](z→ab 贡献 a)，cnt[1][t] = cnt[0][t-1] + cnt[25][t-1](b 来自 a 和 z)。初始 cnt[i][0] = 字符串中字母 i 的个数。答案 = sum cnt[i][t] mod p。时间 O(26·t)。

MOD = 10 ** 9 + 7

def transformations_length(word: str, t: int) -> int:
    cnt = [0] * 26
    for c in word:
        cnt[ord(c) - ord('a')] += 1
    for _ in range(t):
        nxt = [0] * 26
        for i in range(25):
            nxt[i + 1] = (nxt[i + 1] + cnt[i]) % MOD
        # z -> a + b
        nxt[0] = (nxt[0] + cnt[25]) % MOD
        nxt[1] = (nxt[1] + cnt[25]) % MOD
        cnt = nxt
    return sum(cnt) % MOD

class Solution {
    static final int MOD = 1_000_000_007;
    public int transformationsLength(String word, int t) {
        long[] cnt = new long[26];
        for (char c : word.toCharArray()) cnt[c - 'a']++;
        for (int s = 0; s < t; s++) {
            long[] nxt = new long[26];
            for (int i = 0; i < 25; i++) nxt[i + 1] = (nxt[i + 1] + cnt[i]) % MOD;
            nxt[0] = (nxt[0] + cnt[25]) % MOD;
            nxt[1] = (nxt[1] + cnt[25]) % MOD;
            cnt = nxt;
        }
        long s = 0; for (long v : cnt) s = (s + v) % MOD;
        return (int) s;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
    static constexpr long long MOD = 1000000007;
public:
    int transformationsLength(string word, int t) {
        vector<long long> cnt(26, 0);
        for (char c : word) cnt[c - 'a']++;
        for (int s = 0; s < t; s++) {
            vector<long long> nxt(26, 0);
            for (int i = 0; i < 25; i++) nxt[i + 1] = (nxt[i + 1] + cnt[i]) % MOD;
            nxt[0] = (nxt[0] + cnt[25]) % MOD;
            nxt[1] = (nxt[1] + cnt[25]) % MOD;
            cnt = nxt;
        }
        long long total = 0;
        for (auto v : cnt) total = (total + v) % MOD;
        return (int) total;
    }
};

02Count Subsequences

In the context of training a machine learning model for data pattern detection and categorization, there is a dataset represented as an array of n integers, arr[i], where 1A subsequence of a given array can be defined as a sequence that results from removing elements from the array at any position without altering the relative order of the remaining elements. An empty subsequence contains no elements. The Minimum Excludant (MEX) of a sequence is the smallest non-negative integer that is absent from the sequence. The MEX of an empty subsequence is zero. **Function Description** Complete the function countSubsequencesin the editor.countSubsequences` has the following parameters:

List arr: an array of integers
int l: the lower bound of the range
int r: the upper bound of the range Returns int: the number of subsequences with MEX within the range [l, r], modulo (10⁹ + 7)

Constraints

1≤n≤3*10⁵
0≤arr[i]≤10⁹
0≤l≤r≤10⁹

Example 1

Input:

arr = [0, 1, 2]
l = 1
r = 2

Output:

Explanation: The Minimum Excludant (MEX) for all possible subsequences is demonstrated as follows:

An empty subsequence ([]) has a MEX of 0.
A subsequence ([0]) has a MEX of 1.
A subsequence ([1]) has a MEX of 0.
A subsequence ([2]) has a MEX of 0.
For the subsequence ([0, 1]), the MEX is 2.
In the case of ([0, 2]), the MEX is 1.
In the case of ([1, 2]), the MEX is 0.
Finally, when considering the subsequence [0,1,2], the MEX is 3, There are 2 subsequences with MEX of 1 and 1 subsequence with a MEX of 2. Hence, the answer is 1+2=3.

解法

设 f(k) = MEX 恰好 = k 的子序列数。MEX=k 等价于：子序列包含 0..k-1 中每个值至少一次，且不包含 k。设 c[v] = arr 中值为 v 的元素数。则 f(k) = ∏_{v=0}^{k-1}(2^{c[v]}-1) · 1^{c[k]} · 2^{(剩余元素数, 值 > k)}。注意"不包含 k"乘 1(不选这些位置)，"剩余值 > k 任意"乘 2^c[>k]。逐 k 累加 l ≤ k ≤ r 的 f(k) mod 1e9+7。时间 O(n + (r-l+1))。

from collections import Counter
from typing import List

MOD = 10 ** 9 + 7

def count_subsequences(arr: List[int], l: int, r: int) -> int:
    n = len(arr)
    cnt = Counter(arr)
    max_v = max(r + 1, max(cnt) + 1 if cnt else 1)
    # precompute powers of 2 mod
    pow2 = [1] * (n + 1)
    for i in range(1, n + 1):
        pow2[i] = pow2[i - 1] * 2 % MOD
    # prefix product of (2^c[v]-1) for v=0..k-1
    # and count of elements with value >= k
    total = 0
    prefix_prod = 1
    elements_with_value_gt_k = sum(cnt[v] for v in cnt if v > 0)  # elements with v > 0
    # Use total - cumulative cnt[0..k]
    cum_le_k = 0
    for k in range(0, max_v + 1):
        # at this point: prefix_prod = ∏_{v=0}^{k-1}(2^c[v]-1)
        # elements with value > k = n - cum_le_k - cnt[k]
        c_k = cnt.get(k, 0)
        rest = n - cum_le_k - c_k
        # subseq with MEX = k: prefix_prod * 1 (none of k) * 2^rest (any subset of v > k)
        if l <= k <= r:
            total = (total + prefix_prod * pow2[rest]) % MOD
        # advance: include v = k now
        prefix_prod = prefix_prod * ((pow2[c_k] - 1) % MOD) % MOD
        cum_le_k += c_k
        if prefix_prod == 0 and k >= r:
            break
    return total

import java.util.*;

class Solution {
    static final long MOD = 1_000_000_007L;
    public int countSubsequences(List<Integer> arr, int l, int r) {
        int n = arr.size();
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int v : arr) cnt.merge(v, 1, Integer::sum);
        int maxV = r + 1;
        for (int v : cnt.keySet()) maxV = Math.max(maxV, v + 1);
        long[] pow2 = new long[n + 1];
        pow2[0] = 1;
        for (int i = 1; i <= n; i++) pow2[i] = pow2[i - 1] * 2 % MOD;
        long total = 0, prefixProd = 1;
        int cumLeK = 0;
        for (int k = 0; k <= maxV; k++) {
            int cK = cnt.getOrDefault(k, 0);
            int rest = n - cumLeK - cK;
            if (l <= k && k <= r) total = (total + prefixProd * pow2[rest]) % MOD;
            prefixProd = prefixProd * ((pow2[cK] - 1 + MOD) % MOD) % MOD;
            cumLeK += cK;
            if (prefixProd == 0 && k >= r) break;
        }
        return (int) total;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
    static constexpr long long MOD = 1000000007;
public:
    int countSubsequences(vector<int>& arr, int l, int r) {
        int n = arr.size();
        unordered_map<int,int> cnt;
        for (int v : arr) cnt[v]++;
        int maxV = r + 1;
        for (auto& [k, v] : cnt) maxV = max(maxV, k + 1);
        vector<long long> pow2(n + 1, 1);
        for (int i = 1; i <= n; i++) pow2[i] = pow2[i - 1] * 2 % MOD;
        long long total = 0, prefixProd = 1;
        int cumLeK = 0;
        for (int k = 0; k <= maxV; k++) {
            int cK = cnt.count(k) ? cnt[k] : 0;
            int rest = n - cumLeK - cK;
            if (k >= l && k <= r) total = (total + prefixProd * pow2[rest]) % MOD;
            prefixProd = prefixProd * ((pow2[cK] - 1 + MOD) % MOD) % MOD;
            cumLeK += cK;
            if (prefixProd == 0 && k >= r) break;
        }
        return (int) total;
    }
};

03Digit Sum

There is a lottery with c coupons and p participants. Each participant picks exactly one coupon. Coupons are numbered from lowLimit to highLimit, inclusive. The winner of the lottery is any participant who owns a coupon with the sum of digits s written on it. If there is more than one winner, then the prize is split equally among them.

Determine s in such a way that there is at least one winner, and the prize is split among the most participants.
Also determine how many ways the required sum s can be chosen, so that the lottery is split among the maximum number of participants. Function Description Complete the function waysToChooseSum in the editor below. The function must return an array of long integers with 2 elements:
The total number of ways to choose sum so that maximum possible participants win the lottery.
The number of participants who will win the lottery. waysToChooseSum has the following parameter(s):
long lowLimit: a long integer, the starting number of the lottery coupons
long highLimit: a long integer, the ending number of the lottery coupons

Constraints

1 ≤ lowLimit < highLimit ≤ 10¹⁸

Pro解法 · 三语代码 · 复杂度分析

边界讨论 + 面试官追问 · $98 / 一年解锁

Pro 会员

解锁全部 1 道题的解法

题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.

Pro 解锁全部

📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
📊个人 dashboard + 进度可视化 + 14 天活跃图
📝题目笔记跨设备同步 + 个人复盘库
🔓随时取消下次续费, Stripe Customer Portal 自助管理

$12/月($98/年, 一次付清省 32%)

≈ 北美 SWE 工资 10 分钟 · LeetCode Premium $35/月的 23%

立即解锁 $98/年已是会员, 去登录