# 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);
}