Skip to main content
Talentd

Find All Good Strings - Solution & Explanation

HardStringDynamic ProgrammingString Matching23 min readAsked at: Google, Dunzo
Practice this 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.

Approach Overview

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.

Approach 1: Dynamic Programming with Automata

This approach involves the use of dynamic programming combined with an automaton to identify occurrences of the 'evil' substring efficiently. The fundamental idea is to construct an automaton that helps in checking the presence of the evil substring while generating potential 'good' strings between s1 and s2.

The strategy is to use a 3D DP array: dp[pos][evil_length][bounded], where:

  • pos denotes the current position in the string being considered.
  • evil_length is the length of the substring in the automaton matching the of the evil string.
  • bounded is a flag indicating whether the current string prefix is tightly bounded by s1 and s2.

The automaton is utilized to efficiently transition between states based on the current character appended, reducing the time complexity associated with substring checking.

The above Python solution uses a KMP-based automaton to efficiently process and transition states to check for occurrences of the evil substring within potential good strings. The state transitions are precomputed in the KMPAutomaton class, allowing for quick look-up and decision making during the DP recursion. The DP function dfs manages the recursive exploration of possible good strings, accounting for boundaries implied by s1 and s2, and ensuring that the evil substring does not appear.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n * |evil| * 26) due to processing each position with every character and state transition.

Space Complexity: O(n * |evil| * 2) for the memoization table of the DP states.

Try this approach in the editor →

Approach 2: Dynamic Programming with Character Level Constraints

We can use dynamic programming to solve this problem by considering three conditions for each position in the string: whether it should be bounded by s1, s2, and whether it currently contains the 'evil' substring. We can define a dp[pos][is_bound_s1][is_bound_s2][evil_len] table that keeps track of the number of good strings of length n that start from pos, have or not reached the boundaries s1 and s2 constraints, and the number of characters currently matching with the leading characters of the 'evil' string.

This C code utilizes dynamic programming and recursion to calculate the number of 'good' strings. We create a 4D dp array to store probabilities of acquiring 'good' strings up to a particular index with respect to s1 and s2 boundaries and the match length with 'evil'. The logic iteratively checks each character between given bounds and determines the next state recursively. The final result is computed efficiently using memoization.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * 2 * 2 * m) where n is length of s1/s2, m is length of 'evil'
Space Complexity: O(n * 2 * 2 * m)

Try this approach in the editor →

Approach 3: String Matching with KMP for 'Evil' Substring

We can optimize the solution by employing the KMP algorithm to check for the 'evil' substring. While iterating through potential strings, instead of directly looking for substrings, use the KMP partial match table to efficiently find matching 'evil' patterns. This approach also integrates with dynamic programming to manage state transitions.

This version of the C solution enhances the search operation by incorporating a KMP-based algorithm to ascertain the presence of 'evil'. It builds an LPS (Longest Prefix Suffix) array for 'evil' to guide the substring search while iterating character choices. This enables efficient matching in dynamically generating strings.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * 2 * 2 * m), Space Complexity: O(n * 2 * 2 * m)

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Automata

Time Complexity: O(n * |evil| * 26) due to processing each position with every character and state transition.

Space Complexity: O(n * |evil| * 2) for the memoization table of the DP states.

Dynamic Programming with Character Level Constraints

Time Complexity: O(n * 2 * 2 * m) where n is length of s1/s2, m is length of 'evil'
Space Complexity: O(n * 2 * 2 * m)

String Matching with KMP for 'Evil' Substring

Time Complexity: O(n * 2 * 2 * m), Space Complexity: O(n * 2 * 2 * m)

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DP with Character Level ConstraintsO(n * m * 26)O(n * m * 4)Good starting point to understand lexicographic bounds and DP state transitions.
DP with AutomataO(n * m * 26)O(m * 26)Optimal approach when substring detection must be fast during DP transitions.
KMP-based Evil Substring MatchingO(m) preprocessing + O(n * m * 26)O(m)Best when integrating efficient substring matching into DP using prefix function.

Video Solution

LeetCode 1397. Find All Good Strings • Happy Coding • 2,689 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Find All Good Strings easy or hard?
Find All Good Strings is classified as a Hard problem on LeetCode. It combines multiple advanced ideas: lexicographic digit DP, substring matching with KMP, and state optimization. Understanding how these techniques interact is the main challenge.
Find All Good Strings Python/Java solution
Python and Java implementations typically use memoized recursion or bottom-up DP with a KMP prefix array. The code constructs strings character by character, enforces lexicographic bounds from s1 and s2, and updates the current match length of the 'evil' substring using KMP transitions.
How to solve Find All Good Strings in O(n * m * 26)?
Use dynamic programming where the state includes the current index, the number of matched characters from the 'evil' substring, and flags for lower and upper lexicographic bounds. Precompute the KMP LPS array and transition states for substring matching. For each position, iterate through valid characters and update the DP state using the automaton.
What is the best approach for Find All Good Strings?
The most efficient solution combines dynamic programming with a KMP-based automaton for the forbidden substring. The DP tracks the index, matched prefix length of 'evil', and whether the current prefix is still bounded by s1 or s2. Precomputing transitions using KMP ensures substring checks are constant time during DP. This results in O(n * m * 26) time complexity.
Is Find All Good Strings asked at Google/Amazon/Meta?
Hard string DP and automaton problems like this commonly appear in interviews at companies such as Google, Amazon, and Meta. The problem tests knowledge of dynamic programming, lexicographic constraints, and advanced string matching techniques like KMP.
What data structure is used in Find All Good Strings?
The solution mainly uses dynamic programming tables and a KMP prefix (LPS) array. The DP tracks states for string construction, while the prefix array enables efficient substring matching for the 'evil' pattern during transitions.
What is the time complexity of Find All Good Strings?
The optimal solution runs in O(n * m * 26) time, where n is the target string length and m is the length of the 'evil' substring. For each position, the algorithm tries up to 26 characters and updates the KMP match state. Space complexity is typically O(n * m * 4) with memoization or O(m * 26) for the automaton.

Ready to solve this problem?

Practice Find All Good Strings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring