Number of Strings Which Can Be Rearranged to Contain Substring - Video Solutions

Problem Overview: You are given an integer n and must count how many lowercase strings of length n can be rearranged so that the substring "leet" appears. Because rearrangement is allowed, the task becomes a counting problem: the string must contain at least one l, two e's, and one t. Any valid multiset of characters that satisfies these minimum counts can always be rearranged so that "leet" appears as a contiguous substring.

Approach 1: Counting Permutations and Repetitions (Combinatorics) (Time: O(1), Space: O(1))

This approach treats the problem purely as a combinatorics counting task. A valid string must contain at least the characters required to build "leet": one l, two e's, and one t. The remaining n - 4 positions can contain any lowercase letter. The challenge is counting all strings that satisfy these minimum requirements without double counting. The typical technique uses inclusion–exclusion: start from the total number of strings 26^n, then subtract cases where constraints are violated (missing l, missing t, or fewer than two e's). Handling the e condition requires counting both zero and one occurrence cases. Modular arithmetic keeps values within limits. This method relies heavily on combinatorics and math insights and works in constant time once formulas are derived.

Approach 2: Dynamic Programming with String Constraints (Time: O(n), Space: O(1))

The dynamic programming solution builds the string character by character while tracking how many required characters have been collected so far. Define a DP state representing counts of the required letters: whether l has appeared, how many e's have appeared (0, 1, or at least 2), and whether t has appeared. At each step, iterate through the 26 possible characters and update the state transitions. Characters that are not l, e, or t simply keep the constraint state unchanged. The DP accumulates the number of valid strings for each prefix length, and the final answer is the state where all constraints are satisfied. Because the number of states is small and fixed, the algorithm runs in linear time with constant memory. This formulation is a classic constraint-counting DP related to dynamic programming.

Recommended for interviews: The combinatorics approach is typically the expected optimal answer because it reduces the problem to counting with inclusion–exclusion and runs in constant time. However, explaining the DP approach first can demonstrate strong reasoning about constraints and state transitions. Showing both methods signals a solid understanding of counting problems and algorithmic modeling.