Find All Good Strings

Find All Good Strings

What is this problem about?

The Find All Good Strings coding problem is an advanced string-counting task. You are given two strings s1 and s2 of length $n$, and a string evil. A "good" string is one that is lexicographically between s1 and s2 (inclusive) and does not contain evil as a substring. Your goal is to find the total count of such good strings, modulo $10^9 + 7$.

Why is this asked in interviews?

This "Hard" difficulty problem is asked by top companies like Google to test a candidate's mastery of Digit Dynamic Programming and String Matching. It is significantly more complex than standard digit DP because the constraint is a pattern match rather than a simple numeric property. It evaluations your ability to combine DP state management with the KMP (Knuth-Morris-Pratt) algorithm to track the "matching state" of the evil string.

Algorithmic pattern used

This problem uses Digit DP with a state that includes:

1. pos: Current character index being filled (0 to $n-1$).
2. tight1: Boolean, whether the string is currently restricted by the prefix of s1.
3. tight2: Boolean, whether the string is currently restricted by the prefix of s2.
4. evil_match_len: The length of the longest prefix of evil that is currently a suffix of the string we are building. You use the KMP state machine to update evil_match_len as you add each character. If evil_match_len ever equals the full length of evil, the current branch is invalid.

Example explanation

$n=2$, s1="aa", s2="az", evil="ba"

1. Start filling the first character.
2. If we pick 'a', it matches s1 prefix (tight1=true) and is less than s2 (tight2=false).
3. Current prefix "a" has 0 match with "ba".
4. Move to second character. We can pick any from 'a' to 'z'.
5. If we pick 'b', string is "ab". Still good.
6. If we were filling a string where evil was "ab", then "ab" would be invalid.

Common mistakes candidates make

• Ignoring KMP: Trying to search for evil using indexOf or a naive search within the DP, which is inefficient.
• Tight constraint errors: Not correctly handling the lower (s1) and upper (s2) bounds simultaneously.
• State explosion: Including unnecessary information in the DP state, leading to memory limit issues.

Interview preparation tip

This problem is essentially "Digit DP on Strings." Practice standard Digit DP first (like "Count numbers with sum of digits = K"). Once comfortable, learn how to integrate a finite state automaton (like KMP) into your DP transitions.