LeetCode #1397 — HARD

Find All Good Strings

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

Solve on LeetCode
The Problem

Problem Statement

Given the strings s1 and s2 of size n and the string evil, return the number of good strings.

A good string has size n, it is alphabetically greater than or equal to s1, it is alphabetically smaller than or equal to s2, and it does not contain the string evil as a substring. Since the answer can be a huge number, return this modulo 109 + 7.

Example 1:

Input: n = 2, s1 = "aa", s2 = "da", evil = "b"
Output: 51 
Explanation: There are 25 good strings starting with 'a': "aa","ac","ad",...,"az". Then there are 25 good strings starting with 'c': "ca","cc","cd",...,"cz" and finally there is one good string starting with 'd': "da". 

Example 2:

Input: n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet"
Output: 0 
Explanation: All strings greater than or equal to s1 and smaller than or equal to s2 start with the prefix "leet", therefore, there is not any good string.

Example 3:

Input: n = 2, s1 = "gx", s2 = "gz", evil = "x"
Output: 2

Constraints:

  • s1.length == n
  • s2.length == n
  • s1 <= s2
  • 1 <= n <= 500
  • 1 <= evil.length <= 50
  • All strings consist of lowercase English letters.
Patterns Used
📊Dynamic Programming→🔎String Matching→

Roadmap

  1. Brute Force Baseline
  2. Core Insight
  3. Algorithm Walkthrough
  4. Edge Cases
  5. Full Annotated Code
  6. Interactive Study Demo
  7. Complexity Analysis
Step 01

Brute Force Baseline

Problem summary: Given the strings s1 and s2 of size n and the string evil, return the number of good strings. A good string has size n, it is alphabetically greater than or equal to s1, it is alphabetically smaller than or equal to s2, and it does not contain the string evil as a substring. Since the answer can be a huge number, return this modulo 109 + 7.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Dynamic Programming · String Matching

Example 1

2
"aa"
"da"
"b"

Example 2

8
"leetcode"
"leetgoes"
"leet"

Example 3

2
"gx"
"gz"
"x"
Step 02

Core Insight

What unlocks the optimal approach

  • Use DP with 4 states (pos: Int, posEvil: Int, equalToS1: Bool, equalToS2: Bool) which compute the number of valid strings of size "pos" where the maximum common suffix with string "evil" has size "posEvil". When "equalToS1" is "true", the current valid string is equal to "S1" otherwise it is greater. In a similar way when equalToS2 is "true" the current valid string is equal to "S2" otherwise it is smaller.
  • To update the maximum common suffix with string "evil" use KMP preprocessing.
Interview move: turn each hint into an invariant you can check after every iteration/recursion step.
Step 03

Algorithm Walkthrough

Iteration Checklist

  1. Define state (indices, window, stack, map, DP cell, or recursion frame).
  2. Apply one transition step and update the invariant.
  3. Record answer candidate when condition is met.
  4. Continue until all input is consumed.
Use the first example testcase as your mental trace to verify each transition.
Step 04

Edge Cases

Minimum Input
Single element / shortest valid input
Validate boundary behavior before entering the main loop or recursion.
Duplicates & Repeats
Repeated values / repeated states
Decide whether duplicates should be merged, skipped, or counted explicitly.
Extreme Constraints
Largest constraint values
Re-check complexity target against constraints to avoid time-limit issues.
Invalid / Corner Shape
Empty collections, zeros, or disconnected structures
Handle special-case structure before the core algorithm path.
Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #1397: Find All Good Strings
class Solution {
  public int findGoodStrings(int n, String s1, String s2, String evil) {
    Integer[][][][] mem = new Integer[n][evil.length()][2][2];
    // nextMatchedCount[i][j] := the number of next matched evil count, where
    // there're j matches with `evil` and the current letter is ('a' + j)
    Integer[][] nextMatchedCount = new Integer[evil.length()][26];
    return count(s1, s2, evil, 0, 0, true, true, getLPS(evil), nextMatchedCount, mem);
  }

  private static final int MOD = 1_000_000_007;

  // Returns the number of good strings for s[i..n), where there're j matches
  // with `evil`, `isS1Prefix` indicates if the current letter is tightly bound
  // for `s1` and `isS2Prefix` indicates if the current letter is tightly bound
  // for `s2`.
  private int count(final String s1, final String s2, final String evil, int i,
                    int matchedEvilCount, boolean isS1Prefix, boolean isS2Prefix, int[] evilLPS,
                    Integer[][] nextMatchedCount, Integer[][][][] mem) {
    // s[0..i) contains `evil`, so don't consider any ongoing strings.
    if (matchedEvilCount == evil.length())
      return 0;
    // Run out of strings, so contribute one.
    if (i == s1.length())
      return 1;
    final int k1 = isS1Prefix ? 1 : 0;
    final int k2 = isS2Prefix ? 1 : 0;
    if (mem[i][matchedEvilCount][k1][k2] != null)
      return mem[i][matchedEvilCount][k1][k2];
    mem[i][matchedEvilCount][k1][k2] = 0;
    final char minChar = isS1Prefix ? s1.charAt(i) : 'a';
    final char maxChar = isS2Prefix ? s2.charAt(i) : 'z';
    for (char c = minChar; c <= maxChar; ++c) {
      final int nextMatchedEvilCount =
          getNextMatchedEvilCount(nextMatchedCount, evil, matchedEvilCount, c, evilLPS);
      mem[i][matchedEvilCount][k1][k2] +=
          count(s1, s2, evil, i + 1, nextMatchedEvilCount, isS1Prefix && c == s1.charAt(i),
                isS2Prefix && c == s2.charAt(i), evilLPS, nextMatchedCount, mem);
      mem[i][matchedEvilCount][k1][k2] %= MOD;
    }
    return mem[i][matchedEvilCount][k1][k2];
  }

  // Returns the lps array, where lps[i] is the length of the longest prefix of
  // pattern[0..i] which is also a suffix of this substring.
  private int[] getLPS(final String pattern) {
    int[] lps = new int[pattern.length()];
    for (int i = 1, j = 0; i < pattern.length(); ++i) {
      while (j > 0 && pattern.charAt(j) != pattern.charAt(i))
        j = lps[j - 1];
      if (pattern.charAt(i) == pattern.charAt(j))
        lps[i] = ++j;
    }
    return lps;
  }

  // j := the next index we're trying to match with `currLetter`
  private int getNextMatchedEvilCount(Integer[][] nextMatchedCount, final String evil, int j,
                                      char currChar, int[] lps) {
    if (nextMatchedCount[j][currChar - 'a'] != null)
      return nextMatchedCount[j][currChar - 'a'];
    while (j > 0 && evil.charAt(j) != currChar)
      j = lps[j - 1];
    return nextMatchedCount[j][currChar - 'a'] = (evil.charAt(j) == currChar ? j + 1 : j);
  }
}
Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Press Step or Run All to begin.
Step 07

Complexity Analysis

Time
O(n × m)
Space
O(n × m)

Approach Breakdown

RECURSIVE
O(2ⁿ) time
O(n) space

Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.

DYNAMIC PROGRAMMING
O(n × m) time
O(n × m) space

Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.

Shortcut: Count your DP state dimensions → that’s your time. Can you drop one? That’s your space optimization.
Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

State misses one required dimension

Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.

Usually fails on: Correctness breaks on cases that differ only in hidden state.

Fix: Define state so each unique subproblem maps to one DP cell.

Related Problems
#1668Maximum Repeating Substringeasy→#2430Maximum Deletions on a Stringhard→#2851String Transformationhard→#3291Minimum Number of Valid Strings to Form Target Imedium→#3292Minimum Number of Valid Strings to Form Target IIhard→