Leetcode Problem 2930. Number of Strings Which Can Be Rearranged to Contain Substring

2930. Number of Strings Which Can Be Rearranged to Contain Substring

Leetcode Solutions

The Principle of Inclusion-Exclusion (PIE)

  1. Calculate the total number of strings of length n using all 26 letters: total = 26^n.
  2. Calculate the number of strings with no 'l': no_l = 25^n.
  3. Calculate the number of strings with no 't': no_t = 25^n.
  4. Calculate the number of strings with no 'e': no_e = 25^n.
  5. Calculate the number of strings with exactly one 'e': one_e = n * 25^(n-1).
  6. Apply PIE to find the number of bad strings:
    • Subtract the sum of individual cases (no 'l', no 't', no 'e', one 'e').
    • Add the sum of intersections of two conditions.
    • Subtract the sum of intersections of three conditions.
  7. Subtract the number of bad strings from the total to get the number of good strings.
  8. Return the number of good strings modulo 10^9 + 7.
UML Thumbnail

Bitmask Dynamic Programming (DP)

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...