We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Strings Which Can Be Rearranged to Contain Substring

Number: 3200

Difficulty: Medium

Paid? No

Companies: Meesho

Problem Description

Given an integer n, we want to count the total number of “good” strings of length n. A string s (consisting of only lowercase English letters) is called good if it is possible to rearrange its characters so that the string contains "leet" as a contiguous substring. In other words, the string must have at least one 'l', at least two 'e's, and at least one 't'. Return the answer modulo 10^9 + 7.

Key Insights

  • The key condition to form “leet” is that the string must contain at least 1 'l', 2 'e's, and 1 't'.
  • Since rearrangement is allowed, the only requirement is on the frequency of these characters.
  • The total number of strings (without any restrictions) is 26^n.
  • Use complementary counting with inclusion–exclusion:
    • Count strings missing the required number of specific characters.
    • Define F_l for strings with no 'l'; F_e for strings with fewer than 2 'e's (i.e. 0 or 1 'e'); and F_t for strings with no 't'.
    • Similarly, count intersections over these sets.
  • Use fast exponentiation (modular exponentiation) to handle powers modulo 10^9+7.

Space and Time Complexity

Time Complexity: O(log n) per exponentiation (a constant number of them, so overall O(log n)).
Space Complexity: O(1).

Solution

We can solve the problem by counting the number of strings that do NOT meet the requirement (i.e. strings that cannot be rearranged to include “leet”) and subtract that from the total number of strings. The idea is to use inclusion–exclusion on three events:

  1. A: The string contains no 'l'.
  2. B: The string contains fewer than 2 occurrences of 'e' (i.e. 0 or 1 occurrence).
  3. C: The string contains no 't'.

Let:

  • Total = 26^n.
  • F_l = count of strings with no 'l' = 25^n.
  • F_e = count of strings with fewer than 2 'e's = 25^n + (n * 25^(n-1))
    (here, 25^n corresponds to strings with 0 'e' and n*25^(n-1) corresponds to strings with exactly 1 'e').
  • F_t = count of strings with no 't' = 25^n.

For intersections:

  • F_l,e: strings with no 'l' and fewer than 2 'e's.
    With no 'l', allowed letters = 25. For no 'e': count = 24^n. For exactly one 'e': count = n * 24^(n-1). So F_l,e = 24^n + n * 24^(n-1).
  • F_l,t: strings with no 'l' and no 't'. Allowed letters = 24, so F_l,t = 24^n.
  • F_e,t: strings with no 't' and fewer than 2 'e's. Allowed letters = 25 (since we only remove 't'), giving F_e,t = 24^n + n * 24^(n-1).
  • F_l,e,t: strings with no 'l', no 't', and fewer than 2 'e's.
    With no 'l' and no 't', allowed letters = 24. For 0 'e': count = 23^n (exclude 'e' as well) and for exactly one 'e': count = n * 23^(n-1). So F_l,e,t = 23^n + n * 23^(n-1).

Finally, by inclusion–exclusion, the number of good strings is:

Good = Total − (F_l + F_e + F_t) + (F_l,e + F_l,t + F_e,t) − F_l,e,t.

All computations are done modulo 10^9+7.

Code Solutions

# Python solution

MOD = 10**9 + 7

# Fast modular exponentiation using built-in pow with modulus
def mod_pow(base, exp):
    return pow(base, exp, MOD)

def countGoodStrings(n):
    # Total number of strings
    total = mod_pow(26, n)
    
    # Count strings with no 'l'
    count_no_l = mod_pow(25, n)
    
    # Count strings with fewer than 2 'e's:
    # Zero 'e's: use 25 letters (all except 'e')
    count_zero_e = mod_pow(25, n)
    # Exactly one 'e': choose one position for 'e' and fill remaining with 25 letters (not e)
    count_one_e = (n * mod_pow(25, n - 1)) % MOD
    count_few_e = (count_zero_e + count_one_e) % MOD
    
    # Count strings with no 't'
    count_no_t = mod_pow(25, n)
    
    # Now intersections:
    # F_l,e: no 'l' and fewer than 2 'e's.
    # Allowed letters after removing 'l': 25 letters.
    # For 0 'e': choose from 24 letters (exclude e as well)
    count_no_l_zero_e = mod_pow(24, n)
    # Exactly one 'e': choose one position for 'e', others from 24 letters
    count_no_l_one_e = (n * mod_pow(24, n - 1)) % MOD
    count_no_l_few_e = (count_no_l_zero_e + count_no_l_one_e) % MOD
    
    # F_l,t: no 'l' and no 't'
    count_no_l_no_t = mod_pow(24, n)
    
    # F_e,t: no 't' and fewer than 2 'e's.
    # Allowed letters after removing 't': 25 letters.
    count_no_t_zero_e = mod_pow(24, n)
    count_no_t_one_e = (n * mod_pow(24, n - 1)) % MOD
    count_no_t_few_e = (count_no_t_zero_e + count_no_t_one_e) % MOD
    
    # F_l,e,t: no 'l', no 't', and fewer than 2 'e's.
    # Allowed letters: remove l and t, so available letters = 24.
    # For 0 'e': then from 23 letters (removing e as well)
    count_no_l_no_t_zero_e = mod_pow(23, n)
    # For exactly one 'e': choose one position for 'e' and fill others from 23 letters
    count_no_l_no_t_one_e = (n * mod_pow(23, n - 1)) % MOD
    count_no_l_no_t_few_e = (count_no_l_no_t_zero_e + count_no_l_no_t_one_e) % MOD
    
    # Apply inclusion-exclusion principle
    result = (total - (count_no_l + count_few_e + count_no_t) 
              + (count_no_l_few_e + count_no_l_no_t + count_no_t_few_e)
              - count_no_l_no_t_few_e) % MOD
    return result

# Example usage:
n = int(input().strip())
print(countGoodStrings(n))
← Back to All Questions