Find All Good Strings - Video Solutions

Problem Overview: You are given two strings s1 and s2 of length n, and a forbidden substring evil. The task is to count how many strings of length n lie lexicographically between s1 and s2 (inclusive) and do not contain evil as a substring.

Approach 1: Dynamic Programming with Character Level Constraints (O(n * m * 26) time, O(n * m * 4) space)

This approach builds the string character by character while maintaining constraints from s1 and s2. A DP state typically tracks index, how many characters of evil have matched so far, and two flags indicating whether the current prefix is still bounded by s1 or s2. For each position, iterate through possible characters ('a' to 'z') within the allowed bounds and update the match length for evil. If the match length reaches len(evil), that branch is discarded. This method combines dynamic programming with prefix checking to prune invalid strings early.

Approach 2: Dynamic Programming with Automata (O(n * m * 26) time, O(m * 26) automaton space)

The optimal strategy builds a finite automaton for the evil string using prefix transitions. Each state represents how many characters of evil are currently matched. When you append a new character, the automaton immediately tells the next state using precomputed transitions. The DP state becomes (index, matchedLen, lowerBound, upperBound). At every step, iterate over valid characters and transition using the automaton. This avoids recomputing prefix matches repeatedly and keeps the DP transitions fast. It heavily relies on string matching concepts combined with dynamic programming.

Approach 3: String Matching with KMP for Evil Substring (O(m) preprocessing, integrated DP O(n * m * 26))

The Knuth-Morris-Pratt (KMP) algorithm is used to preprocess the evil substring by building the LPS (longest prefix suffix) array. This array determines how the match length changes when characters mismatch while constructing candidate strings. During DP transitions, instead of scanning prefixes manually, you update the matched prefix length using the LPS table. This ensures substring detection happens in constant time per transition while avoiding full substring comparisons.

Recommended for interviews: Interviewers usually expect the DP + KMP automaton approach. It shows you understand how to combine lexicographic constraints, stateful substring matching, and memoized DP. Starting with the character-constrained DP helps demonstrate the core idea. Converting the substring check into a KMP-based automaton is the step that turns a slow solution into the optimal one.