Number of Strings Which Can Be Rearranged to Contain Substring
Number of Strings Which Can Be Rearranged to Contain Substring solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number of Strings Which Can Be Rearranged to Contain Substring is a medium coding problem on dynamic programming, math and combinatorics, asked in Google interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Math, Combinatorics
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A string of lowercase English letters is good if its characters can be rearranged so that the result contains "leet" as a contiguous substring. For example "lteer" is good (rearrange it to "leetr"), while "letl" is not — it has only one e.
Given an integer n, return the number of good strings of length n. Since the answer may be large, return it modulo 10^9 + 7.
Example 1
Input: n = 4
Output: 12
Explanation: The good strings of length 4 are exactly the 12 arrangements of the letters l, e, e, t (4! / 2!).
Example 2
Input: n = 10
Output: 83943898
Example 3
Input: n = 3
Output: 0
Explanation: Three letters cannot hold four required characters.
Constraints
1 <= n <= 10^5
Hints for Number of Strings Which Can Be Rearranged to Contain Substring
Hint 1
Order does not matter at all: a string is good exactly when it has at least one
l, at least twoes and at least onet.Hint 2
Count the complement. Let A = no
l, B = fewer than twoes, C = not, and apply inclusion–exclusion to|A ∪ B ∪ C|.Hint 3
|B| = 25^n + n · 25^(n-1)(zeroes, or exactly one in one ofnplaces); intersections shrink the alphabet the same way. Alternatively, run a 12-state DP over (has l, e count capped at 2, has t).
How to solve Number of Strings Which Can Be Rearranged to Contain Substring
Since characters can be rearranged freely, a string is good exactly when its letter counts include l ≥ 1, e ≥ 2, t ≥ 1. Count all 26^n strings and subtract the bad ones with inclusion–exclusion over the three ways to fail.
Approach
- Let A = strings with no
l, B = strings with at most onee, C = strings with not. |A| = |C| = 25^n,|B| = 25^n + n·25^(n-1);|A∩C| = 24^n,|A∩B| = |B∩C| = 24^n + n·24^(n-1);|A∩B∩C| = 23^n + n·23^(n-1).- Bad =
|A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. - Return
(26^n − bad) mod (10^9 + 7), computing every power by fast exponentiation and keeping the result non-negative.
Why it works
Inclusion–exclusion counts each bad string exactly once. For the e condition, "at most one e" splits into no e at all (25 letters everywhere) and exactly one e (choose its position, 25 letters elsewhere); each extra forbidden letter in an intersection removes one more letter from the alphabet.
Complexity
- Time —
O(log n) - Space —
O(1)
Pitfalls
n·25^(n-1)mod p multiplies two numbers that need 64-bit room (or BigInt / a split multiply in JavaScript).- Subtraction under the modulus can be negative — add the modulus back.
- For
n < 4the answer is 0; the formula gives that automatically, but an off-by-one in theeterm will not.
Reference solution
Python
def stringCount(n: int) -> int:
MOD = 10**9 + 7
def p(b, e):
return pow(b, e, MOD)
bad = (3 * p(25, n) + n * p(25, n - 1)) \
- (3 * p(24, n) + 2 * n * p(24, n - 1)) \
+ (p(23, n) + n * p(23, n - 1))
return (p(26, n) - bad) % MODJava
static final long MOD = 1000000007L;
static long pw(long b, long e) {
long r = 1, x = b % MOD;
while (e > 0) {
if ((e & 1) == 1) r = r * x % MOD;
x = x * x % MOD;
e >>= 1;
}
return r;
}
public static int stringCount(int n) {
long bad = (3 * pw(25, n) + (long) n * pw(25, n - 1)) % MOD;
bad = (bad - (3 * pw(24, n) + 2L * n % MOD * pw(24, n - 1)) % MOD + MOD) % MOD;
bad = (bad + pw(23, n) + (long) n * pw(23, n - 1)) % MOD;
return (int) ((pw(26, n) - bad + MOD) % MOD);
}C++
const long long MOD = 1000000007LL;
long long pw(long long b, long long e) {
long long r = 1, x = b % MOD;
while (e > 0) {
if (e & 1) r = r * x % MOD;
x = x * x % MOD;
e >>= 1;
}
return r;
}
int stringCount(int n) {
long long bad = (3 * pw(25, n) + (long long) n * pw(25, n - 1)) % MOD;
bad = (bad - (3 * pw(24, n) + 2LL * n % MOD * pw(24, n - 1)) % MOD + MOD) % MOD;
bad = (bad + pw(23, n) + (long long) n * pw(23, n - 1)) % MOD;
return (int) ((pw(26, n) - bad + MOD) % MOD);
}JavaScript
var stringCount = function(n) {
var MOD = 1000000007;
// a * b mod MOD with every partial product below 2^53.
var mulmod = function(a, b) {
return ((a * (b >>> 16)) % MOD * 65536 + a * (b & 65535)) % MOD;
};
var p = function(b, e) {
var r = 1, x = b % MOD;
while (e > 0) {
if (e & 1) r = mulmod(r, x);
x = mulmod(x, x);
e >>= 1;
}
return r;
};
var bad = (3 * p(25, n) + mulmod(n, p(25, n - 1))) % MOD;
bad = (bad - (3 * p(24, n) + mulmod(2 * n, p(24, n - 1))) % MOD + MOD) % MOD;
bad = (bad + p(23, n) + mulmod(n, p(23, n - 1))) % MOD;
return (p(26, n) - bad + MOD) % MOD;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming