Welcome to Subscribe On Youtube
2930. Number of Strings Which Can Be Rearranged to Contain Substring
Description
You are given an integer n.
A string s is called good if it contains only lowercase English characters and it is possible to rearrange the characters of s such that the new string contains "leet" as a substring.
For example:
- The string
"lteer"is good because we can rearrange it to form"leetr". "letl"is not good because we cannot rearrange it to contain"leet"as a substring.
Return the total number of good strings of length n.
Since the answer may be large, return it modulo 109 + 7.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: n = 4 Output: 12 Explanation: The 12 strings which can be rearranged to have "leet" as a substring are: "eelt", "eetl", "elet", "elte", "etel", "etle", "leet", "lete", "ltee", "teel", "tele", and "tlee".
Example 2:
Input: n = 10 Output: 83943898 Explanation: The number of strings with length 10 which can be rearranged to have "leet" as a substring is 526083947580. Hence the answer is 526083947580 % (109 + 7) = 83943898.
Constraints:
1 <= n <= 105
Solutions
-
class Solution { private final int mod = (int) 1e9 + 7; public int stringCount(int n) { long a = qpow(25, n); long b = a; long c = (qpow(25, n) + n * qpow(25, n - 1) % mod) % mod; long ab = qpow(24, n); long ac = (qpow(24, n) + n * qpow(24, n - 1) % mod) % mod; long bc = ac; long abc = (qpow(23, n) + n * qpow(23, n - 1) % mod) % mod; long tot = qpow(26, n); return (int) ((tot - (a + b + c - ab - ac - bc + abc)) % mod + mod) % mod; } private long qpow(long a, int n) { long ans = 1; for (; n > 0; n >>= 1) { if ((n & 1) == 1) { ans = ans * a % mod; } a = a * a % mod; } return ans; } } -
class Solution { public: int stringCount(int n) { const int mod = 1e9 + 7; using ll = long long; auto qpow = [&](ll a, int n) { ll ans = 1; for (; n; n >>= 1) { if (n & 1) { ans = ans * a % mod; } a = a * a % mod; } return ans; }; ll a = qpow(25, n); ll b = a; ll c = (qpow(25, n) + n * qpow(25, n - 1) % mod) % mod; ll ab = qpow(24, n); ll ac = (qpow(24, n) + n * qpow(24, n - 1) % mod) % mod; ll bc = ac; ll abc = (qpow(23, n) + n * qpow(23, n - 1) % mod) % mod; ll tot = qpow(26, n); return ((tot - (a + b + c - ab - ac - bc + abc)) % mod + mod) % mod; } }; -
class Solution: def stringCount(self, n: int) -> int: mod = 10**9 + 7 a = b = pow(25, n, mod) c = pow(25, n, mod) + n * pow(25, n - 1, mod) ab = pow(24, n, mod) ac = bc = (pow(24, n, mod) + n * pow(24, n - 1, mod)) % mod abc = (pow(23, n, mod) + n * pow(23, n - 1, mod)) % mod tot = pow(26, n, mod) return (tot - (a + b + c - ab - ac - bc + abc)) % mod -
func stringCount(n int) int { const mod int = 1e9 + 7 qpow := func(a, n int) int { ans := 1 for ; n > 0; n >>= 1 { if n&1 == 1 { ans = ans * a % mod } a = a * a % mod } return ans } a := qpow(25, n) b := a c := qpow(25, n) + n*qpow(25, n-1) ab := qpow(24, n) ac := (qpow(24, n) + n*qpow(24, n-1)) % mod bc := ac abc := (qpow(23, n) + n*qpow(23, n-1)) % mod tot := qpow(26, n) return ((tot-(a+b+c-ab-ac-bc+abc))%mod + mod) % mod } -
function stringCount(n: number): number { const mod = BigInt(10 ** 9 + 7); const qpow = (a: bigint, n: number): bigint => { let ans = 1n; for (; n; n >>>= 1) { if (n & 1) { ans = (ans * a) % mod; } a = (a * a) % mod; } return ans; }; const a = qpow(25n, n); const b = a; const c = (qpow(25n, n) + ((BigInt(n) * qpow(25n, n - 1)) % mod)) % mod; const ab = qpow(24n, n); const ac = (qpow(24n, n) + ((BigInt(n) * qpow(24n, n - 1)) % mod)) % mod; const bc = ac; const abc = (qpow(23n, n) + ((BigInt(n) * qpow(23n, n - 1)) % mod)) % mod; const tot = qpow(26n, n); return Number((((tot - (a + b + c - ab - ac - bc + abc)) % mod) + mod) % mod); }