Number of Strings Which Can Be Rearranged to Contain Substring

Problem

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 _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.

Examples

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 % (10^9 + 7) = 83943898.

Constraints

• 1 <= n <= 10^5

Solution

Method 1 – Combinatorics and Inclusion-Exclusion

Intuition

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).

Approach

1. If n < 4, return 0 (not enough letters for "leet").
2. For each string of length n, count the number of ways to select 2 positions for 'e', 1 for 'l', 1 for 't' (order matters for the substring).
3. The rest n-4 positions can be any lowercase letter.
4. The number of ways to arrange the required letters is n! / (2! * (n-4)!) (since there are 2 indistinguishable 'e's).
5. For each arrangement, the remaining n-4 positions can be filled with any of 26 letters.
6. The answer is: C(n,2) * (n-2)*(n-3) * 26**(n-4) (with proper handling for repeated 'e').
7. Use modular arithmetic for large numbers.

Code

C++

const int MOD = 1e9+7;
long long modpow(long long a, long long b, long long m) {
    long long r = 1;
    while (b) {
        if (b & 1) r = r * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return r;
}
vector<long long> fac, ifac;
void init(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;
}
long long C(int n,int k) {
    if (k<0||k>n) return 0;
    return fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;
}
class Solution {
public:
    int numberOfGoodStrings(int n) {
        if (n<4) return 0;
        init(n);
        long long ans = C(n,2)*C(n-2,1)%MOD*C(n-3,1)%MOD;
        ans = ans*modpow(26,n-4,MOD)%MOD;
        return ans;
    }
};

Go

const MOD int = 1e9+7
func modpow(a, b, m int) int {
    res := 1
    for b > 0 {
        if b&1 == 1 {
            res = res * a % m
        }
        a = a * a % m
        b >>= 1
    }
    return res
}
func numberOfGoodStrings(n int) int {
    if n < 4 {
        return 0
    }
    fac := make([]int, n+1)
    ifac := make([]int, n+1)
    fac[0] = 1
    for i := 1; i <= n; i++ {
        fac[i] = fac[i-1] * i % MOD
    }
    ifac[n] = modpow(fac[n], MOD-2, MOD)
    for i := n - 1; i >= 0; i-- {
        ifac[i] = ifac[i+1] * (i+1) % MOD
    }
    C := func(n, k int) int {
        if k < 0 || k > n {
            return 0
        }
        return fac[n] * ifac[k] % MOD * ifac[n-k] % MOD
    }
    ans := C(n, 2) * C(n-2, 1) % MOD * C(n-3, 1) % MOD
    ans = ans * modpow(26, n-4, MOD) % MOD
    return ans
}

Java

class Solution {
    static final int MOD = 1000000007;
    static long[] fac = new long[100005], ifac = new long[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;
    }
    static long pow(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;
    }
    static long C(int n, int k) {
        if (k<0||k>n) return 0;
        return fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;
    }
    public int numberOfGoodStrings(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;
    }
}

Kotlin

class Solution {
    private val MOD = 1_000_000_007L
    private val fac = LongArray(100005) { 1L }
    private val ifac = LongArray(100005) { 1L }
    init {
        for (i in 1 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
    }
    private fun pow(a: Long, b: Long): Long {
        var a = a; var b = b; var r = 1L
        while (b > 0) {
            if (b and 1L == 1L) r = r*a%MOD
            a = a*a%MOD; b = b shr 1
        }
        return r
    }
    private fun C(n: Int, k: Int): Long {
        if (k<0||k>n) return 0L
        return fac[n]*ifac[k]%MOD*ifac[n-k]%MOD
    }
    fun numberOfGoodStrings(n: Int): Int {
        if (n<4) return 0
        var 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()
    }
}

Python

class Solution:
    def numberOfGoodStrings(self, n: int) -> int:
        MOD = 10**9+7
        if n < 4:
            return 0
        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
        def C(a,b):
            if b<0 or b>a: return 0
            return 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

Rust

const MOD: i64 = 1_000_000_007;
impl Solution {
    pub fn number_of_good_strings(n: i32) -> i32 {
        let n = n as usize;
        if n < 4 { return 0; }
        let mut fac = vec![1i64; n+1];
        for i in 1..=n { fac[i] = fac[i-1]*i as i64%MOD; }
        let mut ifac = vec![1i64; n+1];
        ifac[n] = pow(fac[n], MOD-2);
        for i in (0..n).rev() { ifac[i] = ifac[i+1]*(i as i64+1)%MOD; }
        fn pow(mut a: i64, mut b: i64) -> i64 {
            let mut r = 1;
            while b > 0 {
                if b&1 == 1 { r = r*a%MOD; }
                a = a*a%MOD; b >>= 1;
            }
            r
        }
        fn C(fac: &Vec<i64>, ifac: &Vec<i64>, n: usize, k: usize) -> i64 {
            if k>n { return 0; }
            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 as i64-4)%MOD;
        ans as i32
    }
}

TypeScript

class Solution {
    numberOfGoodStrings(n: number): number {
        const MOD = 1e9+7;
        if (n < 4) return 0;
        const fac = Array(n+1).fill(1);
        for (let i = 1; i <= n; ++i) fac[i] = fac[i-1]*i%MOD;
        const ifac = Array(n+1).fill(1);
        ifac[n] = this.pow(fac[n], MOD-2, MOD);
        for (let i = n-1; i >= 0; --i) ifac[i] = ifac[i+1]*(i+1)%MOD;
        const C = (a: number, b: number) => b<0||b>a?0:fac[a]*ifac[b]%MOD*ifac[a-b]%MOD;
        let ans = C(n,2)*C(n-2,1)%MOD*C(n-3,1)%MOD;
        ans = ans*this.pow(26,n-4,MOD)%MOD;
        return ans;
    }
    pow(a: number, b: number, m: number): number {
        let r = 1;
        while (b > 0) {
            if (b&1) r = r*a%m;
            a = a*a%m; b >>= 1;
        }
        return r;
    }
}

Complexity

• ⏰ Time complexity: O(n), for precomputing factorials and inverse factorials up to n.
• 🧺 Space complexity: O(n), for storing factorials and inverse factorials.