Find All Good Strings - Practice Coding Problems

Find All Good Strings - Problem

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 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: n = 2, s1 = "aa", s2 = "da", evil = "b"

› Output: 51

💡 Note: Valid strings are from "aa" to "da" without containing "b": aa, ac, ad, ..., ca, cc, cd, da. Count excludes any string with 'b'.

Example 2 — Evil Substring Blocking

$ Input: n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet"

› Output: 0

💡 Note: Since s1 starts with "leet" and evil is "leet", any valid string would contain the evil substring, so result is 0.

Example 3 — No Evil Match

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

› Output: 2

💡 Note: Valid strings in range [gx, gz] without 'x' are: gy, gz. Total count is 2.

Constraints

1 ≤ n ≤ 500
1 ≤ |evil| ≤ 50
s1.length == s2.length == n
s1 ≤ s2
s1, s2, evil consist only of lowercase letters

Visualization

Tap to expand

Understanding the Visualization

Input

Range [s1, s2], length n, forbidden evil string

Process

Generate valid strings avoiding evil substring

Output

Count of good strings modulo 10^9+7

Key Takeaway

🎯 Key Insight: Use KMP failure function to efficiently track partial matches of the evil substring while building valid strings with dynamic programming.

Asked in

G Google 15 M Microsoft 8 a Amazon 12

This problem combines dynamic programming with string matching algorithms. The key insight is to use the KMP (Knuth-Morris-Pratt) algorithm to efficiently track partial matches of the evil substring while building valid strings character by character. The optimal approach uses DP with states tracking current position, boundary conditions, and KMP state. Time: O(n × |evil| × 26), Space: O(n × |evil|).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Generation	O(26^n × n)	O(n)	Generate all possible strings and validate each one
Dynamic Programming with KMP	O(n × \|evil\| × 26)	O(n × \|evil\|)	Use DP with KMP preprocessing to efficiently track evil substring matches

Brute Force Generation — Algorithm Steps

Generate all strings of length n
Check lexicographic bounds
Check for evil substring
Count valid strings

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all possible strings of length n

Validate

Check bounds and evil substring

Count

Count valid strings

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int MOD = 1000000007;
int count_result = 0;

int isValid(const char* s, const char* s1, const char* s2, const char* evil) {
    return strcmp(s, s1) >= 0 && strcmp(s, s2) <= 0 && strstr(s, evil) == NULL;
}

void generate(char* current, int pos, int n, const char* s1, const char* s2, const char* evil) {
    if (pos == n) {
        current[pos] = '\0';
        if (isValid(current, s1, s2, evil)) {
            count_result = (count_result + 1) % MOD;
        }
        return;
    }
    
    for (char c = 'a'; c <= 'z'; c++) {
        current[pos] = c;
        generate(current, pos + 1, n, s1, s2, evil);
    }
}

int solution(int n, char* s1, char* s2, char* evil) {
    count_result = 0;
    char* current = (char*)malloc((n + 1) * sizeof(char));
    generate(current, 0, n, s1, s2, evil);
    free(current);
    return count_result;
}

int main() {
    int n;
    char s1[501], s2[501], evil[501];
    
    scanf("%d", &n);
    fgets(s1, sizeof(s1), stdin); // consume newline
    fgets(s1, sizeof(s1), stdin);
    s1[strcspn(s1, "\n")] = 0;
    fgets(s2, sizeof(s2), stdin);
    s2[strcspn(s2, "\n")] = 0;
    fgets(evil, sizeof(evil), stdin);
    evil[strcspn(evil, "\n")] = 0;
    
    int result = solution(n, s1, s2, evil);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(26^n × n)

Generate 26^n strings, each requiring O(n) time to validate

✓ Linear Growth

Space Complexity

O(n)

Space for current string being generated

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Generation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler