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 _thetotal number of good strings of length _n.
Since the answer may be large, return it modulo10^9 + 7.
A substring is a contiguous sequence of characters within a string.
Input: n =4Output: 12Explanation: 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".
Input: n =10Output: 83943898Explanation: The number of strings with length 10 which can be rearranged to have "leet" as a substring is526083947580. Hence the answer is526083947580%(10^9+7)=83943898.
To rearrange a string to contain “leet” as a substring, the string must have at least 2 ’e’, 1 ’l’, and 1 ’t’. The rest of the characters can be any lowercase letter. We count the number of ways to choose positions for these required letters and fill the rest arbitrarily, then multiply by the number of ways to permute the required letters (since “leet” can appear anywhere as a substring after rearrangement).
constint MOD =1e9+7;
longlongmodpow(longlong a, longlong b, longlong m) {
longlong r =1;
while (b) {
if (b &1) r = r * a % m;
a = a * a % m;
b >>=1;
}
return r;
}
vector<longlong> fac, ifac;
voidinit(int n) {
fac.assign(n+1,1); ifac.assign(n+1,1);
for (int i=1;i<=n;++i) fac[i]=fac[i-1]*i%MOD;
ifac[n]=modpow(fac[n],MOD-2,MOD);
for (int i=n-1;i>=0;--i) ifac[i]=ifac[i+1]*(i+1)%MOD;
}
longlongC(int n,int k) {
if (k<0||k>n) return0;
return fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;
}
classSolution {
public:int numberOfGoodStrings(int n) {
if (n<4) return0;
init(n);
longlong ans = C(n,2)*C(n-2,1)%MOD*C(n-3,1)%MOD;
ans = ans*modpow(26,n-4,MOD)%MOD;
return ans;
}
};
classSolution {
staticfinalint MOD = 1000000007;
staticlong[] fac =newlong[100005], ifac =newlong[100005];
static {
fac[0]= 1;
for (int i = 1; i < fac.length; ++i) fac[i]= fac[i-1]*i%MOD;
ifac[fac.length-1]= pow(fac[fac.length-1], MOD-2);
for (int i = fac.length-2; i >= 0; --i) ifac[i]= ifac[i+1]*(i+1)%MOD;
}
staticlongpow(long a, long b) {
long r = 1;
while (b > 0) {
if ((b&1)==1) r = r*a%MOD;
a = a*a%MOD;
b >>= 1;
}
return r;
}
staticlongC(int n, int k) {
if (k<0||k>n) return 0;
return fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;
}
publicintnumberOfGoodStrings(int n) {
if (n<4) return 0;
long ans = C(n,2)*C(n-2,1)%MOD*C(n-3,1)%MOD;
ans = ans*pow(26,n-4)%MOD;
return (int)ans;
}
}
classSolution {
privateval MOD = 1_000_000_007L
privateval fac = LongArray(100005) { 1L }
privateval ifac = LongArray(100005) { 1L }
init {
for (i in1 until fac.size) fac[i] = fac[i-1]*i%MOD
ifac[fac.size-1] = pow(fac[fac.size-1], MOD-2)
for (i in fac.size-2 downTo 0) ifac[i] = ifac[i+1]*(i+1)%MOD
}
privatefunpow(a: Long, b: Long): Long {
var a = a; var b = b; var r = 1Lwhile (b > 0) {
if (b and 1L==1L) r = r*a%MOD
a = a*a%MOD; b = b shr 1 }
return r
}
privatefunC(n: Int, k: Int): Long {
if (k<0||k>n) return0Lreturn fac[n]*ifac[k]%MOD*ifac[n-k]%MOD
}
funnumberOfGoodStrings(n: Int): Int {
if (n<4) return0var ans = C(n,2)*C(n-2,1)%MOD*C(n-3,1)%MOD
ans = ans*pow(26,(n-4).toLong())%MOD
return ans.toInt()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution:
defnumberOfGoodStrings(self, n: int) -> int:
MOD =10**9+7if n <4:
return0 fac = [1]*(n+1)
for i in range(1, n+1):
fac[i] = fac[i-1]*i%MOD
ifac = [1]*(n+1)
ifac[n] = pow(fac[n], MOD-2, MOD)
for i in range(n-1, -1, -1):
ifac[i] = ifac[i+1]*(i+1)%MOD
defC(a,b):
if b<0or b>a: return0return fac[a]*ifac[b]%MOD*ifac[a-b]%MOD
ans = C(n,2)*C(n-2,1)%MOD*C(n-3,1)%MOD
ans = ans*pow(26,n-4,MOD)%MOD
return ans
constMOD: i64=1_000_000_007;
impl Solution {
pubfnnumber_of_good_strings(n: i32) -> i32 {
let n = n asusize;
if n <4 { return0; }
letmut fac =vec![1i64; n+1];
for i in1..=n { fac[i] = fac[i-1]*i asi64%MOD; }
letmut ifac =vec![1i64; n+1];
ifac[n] = pow(fac[n], MOD-2);
for i in (0..n).rev() { ifac[i] = ifac[i+1]*(i asi64+1)%MOD; }
fnpow(mut a: i64, mut b: i64) -> i64 {
letmut r =1;
while b >0 {
if b&1==1 { r = r*a%MOD; }
a = a*a%MOD; b >>=1;
}
r
}
fnC(fac: &Vec<i64>, ifac: &Vec<i64>, n: usize, k: usize) -> i64 {
if k>n { return0; }
fac[n]*ifac[k]%MOD*ifac[n-k]%MOD }
let ans = C(&fac,&ifac,n,2)*C(&fac,&ifac,n-2,1)%MOD*C(&fac,&ifac,n-3,1)%MOD*pow(26,n asi64-4)%MOD;
ans asi32 }
}