2930. Number of Strings Which Can Be Rearranged to Contain Substring LeetCode Solution
In this guide, you will get 2930. Number of Strings Which Can Be Rearranged to Contain Substring LeetCode Solution with the best time and space complexity. The solution to Number of Strings Which Can Be Rearranged to Contain Substring problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Strings Which Can Be Rearranged to Contain Substring
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”.
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
Complexity Analysis
Time Complexity: O(\log n)
Space Complexity: O(1)
2930. Number of Strings Which Can Be Rearranged to Contain Substring LeetCode Solution in C++
class Solution {
public:
int stringCount(int n) {
// There're three invalid conditions:
// a. count('l') == 0
// b. count('e') < 2
// c. count('t') == 0
//
// By Principle of Inclusion-Exclusion (PIE):
// ans = allCount - a - b - c + ab + ac + bc - abc
const long allCount = modPow(26, n);
const long a = modPow(25, n);
const long b = modPow(25, n);
const long c = modPow(25, n) + n * modPow(25, n - 1);
const long ab = modPow(24, n) + n * modPow(24, n - 1);
const long ac = modPow(24, n);
const long bc = modPow(24, n) + n * modPow(24, n - 1);
const long abc = modPow(23, n) + n * modPow(23, n - 1);
return ((allCount - a - b - c + ab + ac + bc - abc) % kMod + kMod) % kMod;
}
private:
static constexpr int kMod = 1'000'000'007;
long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x % kMod, (n - 1)) % kMod;
return modPow(x * x % kMod, (n / 2)) % kMod;
}
}; /* code provided by PROGIEZ */
2930. Number of Strings Which Can Be Rearranged to Contain Substring LeetCode Solution in Java
class Solution {
public int stringCount(int n) {
// There're three invalid conditions:
// a. count('l') == 0
// b. count('e') < 2
// c. count('t') == 0
//
// By Principle of Inclusion-Exclusion (PIE):
// ans = allCount - a - b - c + ab + ac + bc - abc
final long allCount = modPow(26, n);
final long a = modPow(25, n);
final long b = modPow(25, n);
final long c = modPow(25, n) + n * modPow(25, n - 1);
final long ab = modPow(24, n) + n * modPow(24, n - 1);
final long ac = modPow(24, n);
final long bc = modPow(24, n) + n * modPow(24, n - 1);
final long abc = modPow(23, n) + n * modPow(23, n - 1);
return (int) (((allCount - a - b - c + ab + ac + bc - abc) % kMod + kMod) % kMod);
}
private static final int kMod = 1_000_000_007;
private long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x, n - 1) % kMod;
return modPow(x * x % kMod, n / 2);
}
} // code provided by PROGIEZ
2930. Number of Strings Which Can Be Rearranged to Contain Substring LeetCode Solution in Python
class Solution:
def stringCount(self, n: int) -> int:
# There're three invalid conditions:
# a. count('l') == 0
# b. count('e') < 2
# c. count('t') == 0
#
# By Principle of Inclusion-Exclusion (PIE):
# ans = allCount - a - b - c + ab + ac + bc - abc
kMod = 1_000_000_007
allCount = pow(26, n, kMod)
a = pow(25, n, kMod)
b = pow(25, n, kMod)
c = pow(25, n, kMod) + n * pow(25, n - 1, kMod)
ab = pow(24, n, kMod) + n * pow(24, n - 1, kMod)
ac = pow(24, n, kMod)
bc = pow(24, n, kMod) + n * pow(24, n - 1, kMod)
abc = pow(23, n, kMod) + n * pow(23, n - 1, kMod)
return (allCount - a - b - c + ab + ac + bc - abc) % kMod # code by PROGIEZ
