Number of Strings Which Can Be Rearranged to Contain Substring

Medium
1645.

Number of Strings Which Can Be Rearranged to Contain Substring

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.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var stringCount = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Order does not matter at all: a string is good exactly when it has at least one l, at least two es and at least one t.

  2. Hint 2

    Count the complement. Let A = no l, B = fewer than two es, C = no t, and apply inclusion–exclusion to |A ∪ B ∪ C|.

  3. Hint 3

    |B| = 25^n + n · 25^(n-1) (zero es, or exactly one in one of n places); 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

  1. Let A = strings with no l, B = strings with at most one e, C = strings with no t.
  2. |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).
  3. Bad = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|.
  4. 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 < 4 the answer is 0; the formula gives that automatically, but an off-by-one in the e term 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) % MOD

Java

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