Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Number of Strings Which Can Be Rearranged to Contain Substring solution and explanation

MediumCombinatoricsDynamic ProgrammingMath9 min read57.0% acceptanceUpdated 9 Apr 2026
Asked atMeesho
Practise Number of Strings Which Can Be Rearranged to Contain Substring
11:00
2930. Number of Strings Which Can Be Rearranged to Contain Substring | DP | BiWeekly 117Tech Courses · 11:00 · 852 viewsWatch on YouTube
6 more videos on this problem
  1. 2930. Number of Strings Which Can Be Rearranged to Contain Substring | DP | BiWeekly 117Tech Courses · 11:00 · 852 views
  2. 2930. Number of Strings Which Can Be Rearranged to Contain Substring | Leetcode Biweekly 117codingMohan · 30:29 · 796 views
  3. 2930. Number of Strings Which Can Be Rearranged to Contain Substring || Leetcode || Two MethodsAshish Kumar · 28:50 · 631 views
  4. Leetcode 2930. Number of Strings Which Can Be Rearranged to Contain SubstringElite Code · 41:57 · 311 views
  5. 【每日一题】LeetCode 2930. Number of Strings Which Can Be Rearranged to Contain SubstringHuifeng Guan · 14:44 · 292 views
  6. 2930. Number of Strings Which Can Be Rearranged to Contain Substring (Leetcode Medium)Programming Live with Larry · 27:55 · 271 views
  7. 2930 Number of Strings Which Can Be Rearranged to Contain Substring | Biweekly Contest 117NICspy · 7:35 · 214 views

The 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 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

Approach overview

Problem Overview: You are given an integer n and must count how many lowercase strings of length n can be rearranged so that the substring "leet" appears. Because rearrangement is allowed, the task becomes a counting problem: the string must contain at least one l, two e's, and one t. Any valid multiset of characters that satisfies these minimum counts can always be rearranged so that "leet" appears as a contiguous substring.

Approach 1: Counting Permutations and Repetitions (Combinatorics) (Time: O(1), Space: O(1))

This approach treats the problem purely as a combinatorics counting task. A valid string must contain at least the characters required to build "leet": one l, two e's, and one t. The remaining n - 4 positions can contain any lowercase letter. The challenge is counting all strings that satisfy these minimum requirements without double counting. The typical technique uses inclusion–exclusion: start from the total number of strings 26^n, then subtract cases where constraints are violated (missing l, missing t, or fewer than two e's). Handling the e condition requires counting both zero and one occurrence cases. Modular arithmetic keeps values within limits. This method relies heavily on combinatorics and math insights and works in constant time once formulas are derived.

Approach 2: Dynamic Programming with String Constraints (Time: O(n), Space: O(1))

The dynamic programming solution builds the string character by character while tracking how many required characters have been collected so far. Define a DP state representing counts of the required letters: whether l has appeared, how many e's have appeared (0, 1, or at least 2), and whether t has appeared. At each step, iterate through the 26 possible characters and update the state transitions. Characters that are not l, e, or t simply keep the constraint state unchanged. The DP accumulates the number of valid strings for each prefix length, and the final answer is the state where all constraints are satisfied. Because the number of states is small and fixed, the algorithm runs in linear time with constant memory. This formulation is a classic constraint-counting DP related to dynamic programming.

Recommended for interviews: The combinatorics approach is typically the expected optimal answer because it reduces the problem to counting with inclusion–exclusion and runs in constant time. However, explaining the DP approach first can demonstrate strong reasoning about constraints and state transitions. Showing both methods signals a solid understanding of counting problems and algorithmic modeling.

Approach 1: Counting Permutations and Repetitions

This approach calculates the total number of permutations for strings of length n that can include the substring 'leet' by computing and combining permutations and factorial properties for character placement.

MOD = 1000000007

def power(x, y, p):
    res = 1
    x = x % p
    while y > 0:
        if y & 1:
            res = (res * x) % p
        y = y >> 1
        x = (x * x) % p
    return res

def mod_inverse(n, p):
    return power(n, p - 2, p)

def factorial(n):
    res = 1
    for i in range(2, n + 1):
        res = (res * i) % MOD
    return res

def count_good_strings(n):
    if n < 4:
        return 0

    fact_n = factorial(n)
    fact_4 = factorial(4)
    fact_n_minus_4 = factorial(n - 4)

    return (fact_n * mod_inverse(fact_4 * fact_n_minus_4 % MOD, MOD)) % MOD

n = int(input())
print(count_good_strings(n))
import java.util.Scanner;

public class Main {
    static final int MOD = 1000000007;

    static long power(long x, int y, int p) {
        long res = 1;
        x = x % p;
        while (y > 0) {
            if ((y & 1) == 1)
                res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    static long modInverse(long n, int p) {
        return power(n, p - 2, p);
    }

    static long calculateFactorial(int n) {
        long res = 1;
        for (int i = 2; i <= n; i++)
            res = (res * i) % MOD;
        return res;
    }

    public static long countGoodStrings(int n) {
        if (n < 4) return 0;

        long fact_n = calculateFactorial(n);
        long fact_4 = calculateFactorial(4);
        long fact_n_minus_4 = calculateFactorial(n - 4);

        return (fact_n * modInverse(fact_4 * fact_n_minus_4 % MOD, MOD)) % MOD;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(countGoodStrings(n));
    }
}
#include <iostream>
#define MOD 1000000007

using namespace std;

typedef long long ll;

ll power(ll x, int y, int p) {
    ll res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

ll modInverse(ll n, int p) {
    return power(n, p - 2, p);
}

ll calculateFactorial(int n) {
    ll res = 1;
    for (int i = 2; i <= n; i++)
        res = (res * i) % MOD;
    return res;
}

ll countGoodStrings(int n) {
    if (n < 4) return 0;

    ll fact_n = calculateFactorial(n);
    ll fact_4 = calculateFactorial(4);
    ll fact_n_minus_4 = calculateFactorial(n - 4);

    return (fact_n * modInverse(fact_4 * fact_n_minus_4 % MOD, MOD)) % MOD;
}

int main() {
    int n;
    cin >> n;
    cout << countGoodStrings(n) << endl;
    return 0;
}
const MOD = 1000000007;

function power(x, y, p) {
    let res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

function modInverse(n, p) {
    return power(n, p - 2, p);
}

function factorial(n) {
    let res = 1;
    for (let i = 2; i <= n; i++)
        res = (res * i) % MOD;
    return res;
}

function countGoodStrings(n) {
    if (n < 4) return 0;

    const fact_n = factorial(n);
    const fact_4 = factorial(4);
    const fact_n_minus_4 = factorial(n - 4);

    return (fact_n * modInverse(fact_4 * fact_n_minus_4 % MOD, MOD)) % MOD;
}

const n = parseInt(prompt("Enter the value of n:"));
console.log(countGoodStrings(n));
#include <stdio.h>
#define MOD 1000000007

long long power(long long x, int y, int p) {
    long long res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

long long modInverse(long long n, int p) {
    return power(n, p - 2, p);
}

long long calculateFactorial(int n) {
    long long res = 1;
    for (int i = 2; i <= n; i++)
        res = (res * i) % MOD;
    return res;
}

long long countGoodStrings(int n) {
    long long total = 0;
    if (n < 4) return 0;

    long long fact_n = calculateFactorial(n);
    long long fact_4 = calculateFactorial(4);
    long long fact_n_minus_4 = calculateFactorial(n - 4);

    total = (fact_n * modInverse(fact_4 * fact_n_minus_4 % MOD, MOD)) % MOD;

    return total;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%lld\n", countGoodStrings(n));
    return 0;
}
using System;

public class Program {
    const int MOD = 1000000007;

    public static long Power(long x, int y, int p) {
        long res = 1;
        x = x % p;
        while (y > 0) {
            if ((y & 1) == 1)
                res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    public static long ModInverse(long n, int p) {
        return Power(n, p - 2, p);
    }

    public static long CalculateFactorial(int n) {
        long res = 1;
        for (int i = 2; i <= n; i++)
            res = (res * i) % MOD;
        return res;
    }

    public static long CountGoodStrings(int n) {
        if (n < 4) return 0;

        long fact_n = CalculateFactorial(n);
        long fact_4 = CalculateFactorial(4);
        long fact_n_minus_4 = CalculateFactorial(n - 4);

        return (fact_n * ModInverse(fact_4 * fact_n_minus_4 % MOD, MOD)) % MOD;
    }

    public static void Main() {
        int n = int.Parse(Console.ReadLine());
        Console.WriteLine(CountGoodStrings(n));
    }
}

Using Python's easy-to-read syntax, this approach implements modular arithmetic and factorial-based permutations similarly to previous solutions.

Complexity

Time Complexity: O(n) due to factorial calculations.
Space Complexity: O(1), minimal usage inside this function.

Try this approach in the editor

Approach 2: Dynamic Programming with String Constraints

In dynamic programming, substring constraints are managed systematically, solving smaller subproblems consistently while capturing 'leet' occurrence opportunities.

MOD = 1000000007

# Process dynamic programming state

def count_good_strings_dp(n):
    if n < 4:
        return 0

    # DP table where dp[len][mask] is the number of ways to form a good string up to length len with mask capturing 'leet'
    dp = [[0] * 16 for _ in range(n + 1)]
    dp[0][0] = 1

    # Transition
    for length in range(n):
        for mask in range(16):
            for char in range(4):  # 4 chars because 'leet'
                next_mask = mask | (1 << char)
                dp[length + 1][next_mask] = (dp[length + 1][next_mask] + dp[length][mask]) % MOD

    return sum(dp[n][mask] for mask in range(16) if mask == 15) % MOD  # Mask == 15 indicates presence of 'leet'

n = int(input())
print(count_good_strings_dp(n))

This dynamic programming solution defines states and transitions to track the contribution of each character towards including 'leet' in the string. Each state captures whether 'l', 'e', 'e', 't' are part of any prefix.

Complexity

Time Complexity: O(n * 16), modified by constant. Space Complexity: O(n * 16), due to DP table storage.

Try this approach in the editor

Approach 3: Memorization Search

We design a function dfs(i, l, e, t), which represents the number of good strings that can be formed when the remaining string length is i, and there are at least l characters 'l', e characters 'e' and t characters 't'. The answer is dfs(n, 0, 0, 0).

The execution logic of the function dfs(i, l, e, t) is as follows:

If i = 0, it means that the current string has been constructed. If l = 1, e = 2 and t = 1, it means that the current string is a good string, return 1, otherwise return 0.

Otherwise, we can consider adding any lowercase letter other than 'l', 'e', 't' at the current position, there are 23 in total, so the number of schemes obtained at this time is dfs(i - 1, l, e, t) times 23.

We can also consider adding 'l' at the current position, and the number of schemes obtained at this time is dfs(i - 1, min(1, l + 1), e, t). Similarly, the number of schemes for adding 'e' and 't' are dfs(i - 1, l, min(2, e + 1), t) and dfs(i - 1, l, e, min(1, t + 1)) respectively. Add them up and take the modulus of 10^9 + 7 to get the value of dfs(i, l, e, t).

To avoid repeated calculations, we can use memorization search.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string.

function stringCount(n: number): number {
    const mod = 10 ** 9 + 7;
    const f: number[][][][] = Array.from({ length: n + 1 }, () =>
        Array.from({ length: 2 }, () =>
            Array.from({ length: 3 }, () => Array.from({ length: 2 }, () => -1)),
        ),
    );
    const dfs = (i: number, l: number, e: number, t: number): number => {
        if (i === 0) {
            return l === 1 && e === 2 && t === 1 ? 1 : 0;
        }
        if (f[i][l][e][t] !== -1) {
            return f[i][l][e][t];
        }
        const a = (dfs(i - 1, l, e, t) * 23) % mod;
        const b = dfs(i - 1, Math.min(1, l + 1), e, t);
        const c = dfs(i - 1, l, Math.min(2, e + 1), t);
        const d = dfs(i - 1, l, e, Math.min(1, t + 1));
        return (f[i][l][e][t] = (a + b + c + d) % mod);
    };
    return dfs(n, 0, 0, 0);
}
func stringCount(n int) int {
	const mod int = 1e9 + 7
	f := make([][2][3][2]int, n+1)
	for i := range f {
		for j := range f[i] {
			for k := range f[i][j] {
				for l := range f[i][j][k] {
					f[i][j][k][l] = -1
				}
			}
		}
	}
	var dfs func(i, l, e, t int) int
	dfs = func(i, l, e, t int) int {
		if i == 0 {
			if l == 1 && e == 2 && t == 1 {
				return 1
			}
			return 0
		}
		if f[i][l][e][t] == -1 {
			a := dfs(i-1, l, e, t) * 23 % mod
			b := dfs(i-1, min(1, l+1), e, t)
			c := dfs(i-1, l, min(2, e+1), t)
			d := dfs(i-1, l, e, min(1, t+1))
			f[i][l][e][t] = (a + b + c + d) % mod
		}
		return f[i][l][e][t]
	}
	return dfs(n, 0, 0, 0)
}
Try this approach in the editor

Approach 4: Reverse Thinking + Inclusion-Exclusion Principle

We can consider reverse thinking, that is, calculate the number of strings that do not contain the substring "leet", and then subtract this number from the total.

We divide it into the following cases:

  • Case a: represents the number of schemes where the string does not contain the character 'l', so we have a = 25^n.
  • Case b: similar to a, represents the number of schemes where the string does not contain the character 't', so we have b = 25^n.
  • Case c: represents the number of schemes where the string does not contain the character 'e' or only contains one character 'e', so we have c = 25^n + n times 25^{n - 1}.
  • Case ab: represents the number of schemes where the string does not contain the characters 'l' and 't', so we have ab = 24^n.
  • Case ac: represents the number of schemes where the string does not contain the characters 'l' and 'e' or only contains one character 'e', so we have ac = 24^n + n times 24^{n - 1}.
  • Case bc: similar to ac, represents the number of schemes where the string does not contain the characters 't' and 'e' or only contains one character 'e', so we have bc = 24^n + n times 24^{n - 1}.
  • Case abc: represents the number of schemes where the string does not contain the characters 'l', 't' and 'e' or only contains one character 'e', so we have abc = 23^n + n times 23^{n - 1}.

Then according to the inclusion-exclusion principle, a + b + c - ab - ac - bc + abc is the number of strings that do not contain the substring "leet".

The total number tot = 26^n, so the answer is tot - (a + b + c - ab - ac - bc + abc), remember to take the modulus of 10^9 + 7.

The time complexity is O(log n), and the space complexity is O(1). Here, n is the length of the string.

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);
}
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
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Counting Permutations and Repetitions

Time Complexity: O(n) due to factorial calculations.
Space Complexity: O(1), minimal usage inside this function.

Dynamic Programming with String Constraints

Time Complexity: O(n * 16), modified by constant. Space Complexity: O(n * 16), due to DP table storage.

Memorization Search–
Reverse Thinking + Inclusion-Exclusion Principle–

Complexity analysis

ApproachTimeSpaceWhen to Use
Counting Permutations and Repetitions (Combinatorics)O(1)O(1)Best for deriving a mathematical formula using inclusion-exclusion when constraints involve required character counts.
Dynamic Programming with String ConstraintsO(n)O(1)Useful when modeling the problem as state transitions for required characters or when the combinatorics formula is hard to derive.

Frequently asked questions

Is Number of Strings Which Can Be Rearranged to Contain Substring easy or hard?

This problem is generally rated Medium because the brute counting idea is straightforward but deriving the correct combinatorics formula requires careful handling of constraints like two occurrences of 'e'. Dynamic programming offers a more intuitive but slightly slower alternative.

Number of Strings Which Can Be Rearranged to Contain Substring Python/Java solution

Python, Java, C++, and JavaScript implementations typically compute powers of 26 with modular arithmetic and apply inclusion–exclusion formulas. The DP version uses a small state array updated for each position in the string and works well in Python or Java.

How to solve Number of Strings Which Can Be Rearranged to Contain Substring in O(1)?

Treat the problem as counting valid character multisets. A valid string must contain at least one 'l', two 'e's, and one 't'. Compute the total number of strings (26^n) and subtract invalid cases such as missing 'l', missing 't', or having fewer than two 'e's using inclusion–exclusion. The formula evaluation takes constant time.

What is the best approach for Number of Strings Which Can Be Rearranged to Contain Substring?

The optimal approach uses combinatorics with inclusion–exclusion. Instead of generating strings, count all possible strings (26^n) and subtract cases that violate the required characters for "leet". The final formula runs in O(1) time and O(1) space using modular arithmetic.

Is Number of Strings Which Can Be Rearranged to Contain Substring asked at Google/Amazon/Meta?

Problems combining combinatorics and counting constraints are common in interviews at companies like Google, Amazon, and Meta. Variations of this question appear when evaluating a candidate’s ability to apply inclusion–exclusion, dynamic programming states, and modular arithmetic.

What data structure is used in Number of Strings Which Can Be Rearranged to Contain Substring?

The combinatorics solution does not require special data structures and relies mainly on arithmetic and exponentiation. The dynamic programming solution uses a small DP state table tracking whether 'l' and 't' appear and how many 'e's have been seen so far.

What is the time complexity of Number of Strings Which Can Be Rearranged to Contain Substring?

The combinatorics solution runs in O(1) time because it evaluates a constant number of power and arithmetic operations. A dynamic programming alternative processes the string length sequentially and runs in O(n) time with O(1) space due to a small fixed number of states.

Comments

Next problem · similarCount Vowels PermutationHard
Now write it yourselfClose this page and solve Number of Strings Which Can Be Rearranged to Contain Substring in the editor, without looking.
Practise Number of Strings Which Can Be Rearranged to Contain Substring