Welcome to Subscribe On Youtube
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
Solution 1: 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.
Solution 2: 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.
-
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); }