Number of strings which can be rearranged to contain substring

Math Dynamic Programming Combinatorics

57.0% acceptance

Feb 25, 2026

188

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. Return the total number of good strings of length n. Since the answer may be large, return it modulo 10^9 + 7.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn string_count(n: i32) -> i32 {
    // Good string: count(l) >= 1, count(e) >= 2, count(t) >= 1
    // Use inclusion-exclusion on complement:
    // |bad| = |no_l| + |e_lt_2| + |no_t| - |no_l & e_lt_2| - |no_l & no_t| - |e_lt_2 & no_t| + |no_l & e_lt_2 & no_t|
    const MOD: i64 = 1_000_000_007;
    let n = n as i64;

    fn modpow(mut base: i64, mut exp: i64, modulus: i64) -> i64 {
      let mut result = 1i64;
      base %= modulus;
      while exp > 0 {
        if exp & 1 == 1 { result = result * base % modulus; }
        base = base * base % modulus;
        exp >>= 1;
      }
      result
    }

    let pow26 = |e: i64| -> i64 { modpow(26, e, MOD) };
    let pow25 = |e: i64| -> i64 { modpow(25, e, MOD) };
    let pow24 = |e: i64| -> i64 { modpow(24, e, MOD) };
    let pow23 = |e: i64| -> i64 { modpow(23, e, MOD) };

    // |no_l|: 25^n
    let no_l = pow25(n);
    // |e_lt_2|: strings with count(e) = 0 or 1 = 25^n + n*25^(n-1)
    let e_lt_2 = (pow25(n) + n % MOD * pow25(n - 1) % MOD) % MOD;
    // |no_t|: 25^n
    let no_t = pow25(n);

    // |no_l & e_lt_2|: no 'l', e<=1 → alphabet = {a..z}\{l} = 24 chars
    let no_l_e_lt_2 = (pow24(n) + n % MOD * pow24(n - 1) % MOD) % MOD;
    // |no_l & no_t|: 24^n
    let no_l_no_t = pow24(n);
    // |e_lt_2 & no_t|: no 't', e<=1 → alphabet = {a..z}\{t} = 24 chars
    let e_lt_2_no_t = (pow24(n) + n % MOD * pow24(n - 1) % MOD) % MOD;

    // |no_l & e_lt_2 & no_t|: no 'l', no 't', e<=1 → alphabet = 23 chars
    let all_three = (pow23(n) + n % MOD * pow23(n - 1) % MOD) % MOD;

    let bad = (no_l + e_lt_2 + no_t - no_l_e_lt_2 - no_l_no_t - e_lt_2_no_t + all_three)
      .rem_euclid(MOD);

    let total = pow26(n);
    ((total - bad + MOD) % MOD) as i32
  }
}