Number of Strings Which Can Be Rearranged to Contain Substring

Number of Strings Which Can Be Rearranged to Contain Substring

What is this problem about?

The Number of Strings Which Can Be Rearranged to Contain Substring problem gives you a count n and asks how many strings of length n can be rearranged to contain the substring "leet" (or another given target). Use complementary counting: count strings that cannot contain the required substring, then subtract from the total. This coding problem uses inclusion-exclusion with combinatorics/DP.

Why is this asked in interviews?

Meesho asks this to test the complementary counting technique for complex constraint satisfaction. Directly counting strings that contain "leet" is hard; counting those that don't (via inclusion-exclusion on each missing required character) is cleaner. The math, combinatorics, and dynamic programming interview pattern is demonstrated.

Algorithmic pattern used

Inclusion-exclusion DP. Total strings = 26^n. Use DP where state tracks how much of "leet" has been satisfied. dp[i][j] = number of length-i strings that have satisfied the first j characters of "leet" so far (where "leet" requires at least 1 'l', 2 'e's, and 1 't'). The DP counts satisfied strings; alternatively, count unsatisfied by inclusion-exclusion on "missing l", "missing e (count<2)", "missing t".

Example explanation

n=4. Total = 26^4. "leet" requires: at least 1 'l', at least 2 'e', at least 1 't'. Strings of length 4 that contain at least {l:1, e:2, t:1}: effectively, the string must be a permutation of exactly {l,e,e,t} → 4!/2! = 12 arrangements. But strings can have more characters if n > 4. For n=4 exactly: Answer = 12. For general n: DP-based counting.

Common mistakes candidates make

• Confusing "rearrangement" with "exact match" (rearranged means the characters are present, not necessarily in order).
• Not handling repeated characters in "leet" (two 'e's required).
• Using O(26^n) brute force.
• Incorrect inclusion-exclusion when the target substring has repeated characters.

Interview preparation tip

Complementary counting + DP is powerful for "count strings with required character frequencies." The DP state tracks how many of the required characters have been collected so far. Practice problems involving "strings containing all letters of a target" — they use the same "satisfied prefix count" DP or inclusion-exclusion approach. Memorize the inclusion-exclusion formula for 2-3 overlapping constraints.