Scale Engineer

Number of Strings Which Can Be Rearranged to Contain Substring

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

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

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].

Walkthrough

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

Time

O(n). The main loop runs `n` times, and inside the loop, we perform a constant number of operations (12 states * 4 transitions).

Space

O(1). We use two DP tables of size `2 * 3 * 2`, which is constant space.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem