Number of Strings Which Can Be Rearranged to Contain Substring

MEDIUM

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 10⁹ + 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 % (10⁹ + 7) = 83943898.

Constraints:

1 <= n <= 10⁵

Approaches

Checkout 2 different approaches to solve Number of Strings Which Can Be Rearranged to Contain Substring. Click on different approaches to view the approach and algorithm in detail.

Dynamic Programming

This approach involves building the strings of length n incrementally while keeping track of the necessary character counts. We define a state based on whether we have seen at least one 'l', at least one 't', and how many 'e's we've seen (0, 1, or 2+).

Algorithm

Define a DP state dp[l_flag][e_count][t_flag] to count strings based on the required character counts.
The state parameters are:
- l_flag: 0 for no 'l's, 1 for at least one 'l'.
- e_count: 0, 1, or 2, representing the count of 'e's (capped at 2).
- t_flag: 0 for no 't's, 1 for at least one 't'.
Initialize a DP table dp[2][3][2] with dp[0][0][0] = 1 (for the empty string) and all other states as 0.
Iterate from i = 1 to n to build strings of increasing length.
In each iteration, compute a new_dp table for length i based on the dp table for length i-1.
The transitions are calculated by considering appending a character ('l', 'e', 't', or one of the 23 others) to the strings of the previous length.
After n iterations, the answer is the value in the state that meets all conditions, which is dp[1][2][1].

We use a dynamic programming table, dp[l_flag][e_count][t_flag], to store the number of strings of a certain length that satisfy a specific state. The state is defined by three parameters:

l_flag: 0 if no 'l' has been used, 1 if at least one 'l' has been used.
e_count: The number of 'e's used, capped at 2 (i.e., states are 0, 1, or >=2).
t_flag: 0 if no 't' has been used, 1 if at least one 't' has been used.

The DP table size is 2 x 3 x 2, which is constant. We can optimize space by only storing the counts for the current length, as the counts for length i only depend on length i-1.

All calculations are performed modulo 10^9 + 7.

class Solution {
    public int stringCount(int n) {
        long MOD = 1_000_000_007;
        if (n < 4) return 0;

        // dp[l_flag][e_count][t_flag]
        long[][][] dp = new long[2][3][2];
        dp[0][0][0] = 1; // For the empty string

        for (int i = 0; i < n; i++) {
            long[][][] newDp = new long[2][3][2];
            for (int l = 0; l < 2; l++) {
                for (int e = 0; e < 3; e++) {
                    for (int t = 0; t < 2; t++) {
                        if (dp[l][e][t] == 0) continue;
                        long ways = dp[l][e][t];

                        // Case 1: Append 'l'
                        newDp[1][e][t] = (newDp[1][e][t] + ways) % MOD;

                        // Case 2: Append 'e'
                        newDp[l][Math.min(2, e + 1)][t] = (newDp[l][Math.min(2, e + 1)][t] + ways) % MOD;

                        // Case 3: Append 't'
                        newDp[l][e][1] = (newDp[l][e][1] + ways) % MOD;

                        // Case 4: Append any other character (26 - 3 = 23 choices)
                        newDp[l][e][t] = (newDp[l][e][t] + ways * 23) % MOD;
                    }
                }
            }
            dp = newDp;
        }

        return (int) dp[1][2][1];
    }
}

Complexity Analysis

Time Complexity: O(n). The main loop runs `n` times, and inside the loop, we perform a constant number of operations (12 states * 4 transitions).Space Complexity: O(1). We use two DP tables of size `2 * 3 * 2`, which is constant space.

Pros and Cons

Pros:

More intuitive than combinatorics if you are familiar with DP.
Handles state transitions explicitly and is generally easier to debug.

Cons:

Less efficient than the combinatorics approach, with a time complexity linear in n.

Code Solutions

Checking out 3 solutions in different languages for Number of Strings Which Can Be Rearranged to Contain Substring. Click on different languages to view the code.

class Solution {
private
  final int mod = (int)1 e9 + 7;
private
  Long[][][][] f;
public
  int stringCount(int n) {
    f = new Long[n + 1][2][3][2];
    return (int)dfs(n, 0, 0, 0);
  }
private
  long dfs(int i, int l, int e, int t) {
    if (i == 0) {
      return l == 1 && e == 2 && t == 1 ? 1 : 0;
    }
    if (f[i][l][e][t] != null) {
      return f[i][l][e][t];
    }
    long a = dfs(i - 1, l, e, t) * 23 % mod;
    long b = dfs(i - 1, Math.min(1, l + 1), e, t);
    long c = dfs(i - 1, l, Math.min(2, e + 1), t);
    long d = dfs(i - 1, l, e, Math.min(1, t + 1));
    return f[i][l][e][t] = (a + b + c + d) % mod;
  }
}

Video Solution

Watch the video walkthrough for Number of Strings Which Can Be Rearranged to Contain Substring

Patterns:

MathDynamic ProgrammingCombinatorics