What is the time complexity of Find All Good Strings?

The optimal solution has a time complexity of O(n*m).

What data structures are used to solve Find All Good Strings?

This problem uses String, Dynamic Programming, String Matching. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Find All Good Strings?

Insight 1: Dynamic programming is essential due to overlapping subproblems when counting valid strings based on prefixes and substring avoidance. Memoization helps avoid redundant calculations. Insight 2: KMP algorithm is needed to efficiently precompute the longest proper prefix that is also a suffix (LPS) for the 'evil' string. This allows determining how much of 'evil' has been matched so far as we build our good strings.

Which companies ask LeetCode 1397. Find All Good Strings in interviews?

This problem is frequently asked at Dunzo.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Find All Good Strings - LeetCode 1397 Solution

Q: What is the space complexity of Find All Good Strings?

The space complexity is O(n*m).

Find All Good Strings - Complete Solution Guide

Find All Good Strings is LeetCode problem 1397, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 10 9 + 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"

Detailed Explanation

The problem requires you to find the number of "good" strings of length 'n' that satisfy the following conditions: 1) the string must be lexicographically greater than or equal to 's1', 2) the string must be lexicographically less than or equal to 's2', and 3) the string must not contain 'evil' as a substring. The result needs to be returned modulo 10^9 + 7 to prevent integer overflow. 's1' and 's2' are of length 'n'.

Solution Approach

The solution employs a dynamic programming approach with memoization to count the number of good strings. A helper function `dp(idx, tight1, tight2, evil_match_len)` recursively calculates the number of valid strings starting from index `idx`, considering whether it's tightly bound by `s1` and `s2` (`tight1`, `tight2`) and how much of `evil` has been matched (`evil_match_len`). The KMP algorithm is used to build a transition table that determines the next `evil_match_len` given a character and the current `evil_match_len`. The base cases are when a full match of 'evil' is found (return 0) or a valid string of length n is formed (return 1).

Step-by-Step Algorithm

Step 1: Calculate the LPS (Longest Proper Prefix which is also a Suffix) array for the 'evil' string using the KMP algorithm. This is a pre-processing step.
Step 2: Create a transition table that maps the current match length of 'evil' and the next character to the new match length. This table is derived from the LPS array.
Step 3: Define a recursive function `dp(idx, tight1, tight2, evil_match_len)` that takes the current index in the string being built, tight constraints, and the length of the current match with 'evil' as input.
Step 4: Inside the `dp` function, check the base cases: if `evil_match_len == m` (the length of 'evil'), return 0 because the string contains 'evil' as a substring and isn't valid. If `idx == n` (the length of the string being built is 'n'), return 1, because a valid string has been formed.
Step 5: Iterate through all possible characters for the current position 'idx', considering the tight constraints imposed by 's1' and 's2'.
Step 6: For each character, update the tight constraints and the length of the match with 'evil' using the precomputed transition table.
Step 7: Recursively call the `dp` function with the updated parameters and accumulate the results, taking the modulo at each step to prevent overflow.
Step 8: Memoize the result of each `dp` call to avoid recalculating the same state. This drastically improves performance.
Step 9: Call the `dp` function starting from index 0 with initial tight constraints set to true and `evil_match_len` set to 0.

Key Insights

Insight 1: Dynamic programming is essential due to overlapping subproblems when counting valid strings based on prefixes and substring avoidance. Memoization helps avoid redundant calculations.
Insight 2: KMP algorithm is needed to efficiently precompute the longest proper prefix that is also a suffix (LPS) for the 'evil' string. This allows determining how much of 'evil' has been matched so far as we build our good strings.
Insight 3: Keeping track of whether the current string being built is lexicographically constrained by 's1' and 's2' is crucial. These constraints are handled with 'tight' boolean variables to manage the valid character ranges at each position.

Complexity Analysis

Time Complexity: O(n*m)

Space Complexity: O(n*m)

Topics

This problem involves: String, Dynamic Programming, String Matching.

Companies

Asked at: Dunzo.

Find All Good Strings | LeetCode 1397

Hard

String Dynamic Programming String Matching

Time: O(n*m)Space: O(n*m)

Solution Code

Available in:

class Solution {
    private static final int MOD = 1000000007;

    public int findGoodStrings(int n, String s1, String s2, String evil) {
        int m = evil.length();

        int[] lps = new int[m];
        int j = 0;
        for (int i = 1; i < m; i++) {
            while (j > 0 && evil.charAt(i) != evil.charAt(j)) {
                j = lps[j - 1];
            }
            if (evil.charAt(i) == evil.charAt(j)) {
                j++;
            }
            lps[i] = j;
        }

        int[][] transition = new int[m][26];
        for (j = 0; j < m; j++) {
            for (int i = 0; i < 26; i++) {
                char c = (char) ('a' + i);
                int temp_j = j;
                while (temp_j > 0 && c != evil.charAt(temp_j)) {
                    temp_j = lps[temp_j - 1];
                }
                if (c == evil.charAt(temp_j)) {
                    temp_j++;
                }
                transition[j][i] = temp_j;
            }
        }

        Integer[][][][] memo = new Integer[n][2][2][m];

        return dp(0, 1, 1, 0, n, s1, s2, evil, transition, memo);
    }

    private int dp(int idx, int tight1, int tight2, int evil_match_len, int n, String s1, String s2, String evil, int[][] transition, Integer[][][][] memo) {
        if (evil_match_len == evil.length()) {
            return 0;
        }

        if (idx == n) {
            return 1;
        }

        if (memo[idx][tight1][tight2][evil_match_len] != null) {
            return memo[idx][tight1][tight2][evil_match_len];
        }

        int res = 0;

        int lower_char_code = (tight1 == 1) ? s1.charAt(idx) : 'a';
        int upper_char_code = (tight2 == 1) ? s2.charAt(idx) : 'z';

        for (int char_code = lower_char_code; char_code <= upper_char_code; char_code++) {
            int new_tight1 = (tight1 == 1 && (char_code == s1.charAt(idx))) ? 1 : 0;
            int new_tight2 = (tight2 == 1 && (char_code == s2.charAt(idx))) ? 1 : 0;

            int char_idx = char_code - 'a';
            int next_evil_match_len = transition[evil_match_len][char_idx];

            res = (res + dp(idx + 1, new_tight1, new_tight2, next_evil_match_len, n, s1, s2, evil, transition, memo)) % MOD;
        }

        memo[idx][tight1][tight2][evil_match_len] = res;
        return res;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1397: Find All Good Strings - Detailed explanation and solution approaches.

Topics

String Dynamic Programming String Matching

Companies

Dunzo

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:1397

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Calculate the LPS (Longest Proper Prefix which is also a Suffix) array for the 'evil' string using the KMP algorithm. This is a pre-processing step.
2
Step 2: Create a transition table that maps the current match length of 'evil' and the next character to the new match length. This table is derived from the LPS array.
3
Step 3: Define a recursive function `dp(idx, tight1, tight2, evil_match_len)` that takes the current index in the string being built, tight constraints, and the length of the current match with 'evil' as input.
4
Step 4: Inside the `dp` function, check the base cases: if `evil_match_len == m` (the length of 'evil'), return 0 because the string contains 'evil' as a substring and isn't valid. If `idx == n` (the length of the string being built is 'n'), return 1, because a valid string has been formed.
5
Step 5: Iterate through all possible characters for the current position 'idx', considering the tight constraints imposed by 's1' and 's2'.
6
Step 6: For each character, update the tight constraints and the length of the match with 'evil' using the precomputed transition table.
7
Step 7: Recursively call the `dp` function with the updated parameters and accumulate the results, taking the modulo at each step to prevent overflow.
8
Step 8: Memoize the result of each `dp` call to avoid recalculating the same state. This drastically improves performance.
9
Step 9: Call the `dp` function starting from index 0 with initial tight constraints set to true and `evil_match_len` set to 0.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n*m)

💾

Space Complexity

O(n*m)

📝

Why?

The time complexity is O(n*m) because the `dp` function has `n * 2 * 2 * m` possible states, where n is the length of strings s1 and s2, and m is the length of the evil string. Each state takes constant time to calculate due to the precomputed KMP transition table. The space complexity is O(n*m) because the memoization table stores results for each of the n*m states.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Generate all possible strings of length 'n' between 's1' and 's2' and check each string whether it contains 'evil' as a substring. If it does, increment count.

Time: O(26^n * n * m)Space: O(1)

Trade-offs: This approach is simple to understand but highly inefficient due to the exponential number of possible strings. It is not feasible for large values of 'n'. Use the brute force method only for very small constraint inputs.

✨

Key Insights

1Insight 1: Dynamic programming is essential due to overlapping subproblems when counting valid strings based on prefixes and substring avoidance. Memoization helps avoid redundant calculations.
2Insight 2: KMP algorithm is needed to efficiently precompute the longest proper prefix that is also a suffix (LPS) for the 'evil' string. This allows determining how much of 'evil' has been matched so far as we build our good strings.
3Insight 3: Keeping track of whether the current string being built is lexicographically constrained by 's1' and 's2' is crucial. These constraints are handled with 'tight' boolean variables to manage the valid character ranges at each position.

📚

Key Terms Explained

For Students

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: `evil` is an empty string. The LPS array and transition table will be empty. While the given constraints state evil.length >= 1, a robust solution might handle this gracefully, most likely by returning the number of strings between s1 and s2. This case is implicitly handled correctly by the algorithm.
Edge case 2: `s1` and `s2` are equal, and 'evil' is a substring of `s1`. In this case, the answer should be 0. The algorithm correctly handles this case because when 'evil' is encountered in the dp, it returns 0.
Edge case 3: `s1` and `s2` are equal and 'evil' isn't present, the answer is one. This is correctly handled.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Failing to memoize the results of the `dp` function, leading to exponential time complexity and exceeding time limits.

✗Common mistake 2: Incorrectly calculating the LPS array for the KMP algorithm, resulting in incorrect transition table and ultimately, wrong answers.

✗Common mistake 3: Not considering the tight constraints imposed by 's1' and 's2' at each position, leading to strings outside of the required range.

✗Common mistake 4: Integer overflow by not applying modulo operation during intermediate calculations.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Detecting malicious patterns in network traffic. The 'evil' string could represent a known malicious sequence, and the algorithm can be used to find the number of allowed traffic sequences without the malicious pattern.

🏦Real-world scenario 2: Generating passwords that adhere to certain security policies, such as not containing specific banned substrings. The algorithm can be adapted to count the number of possible valid passwords within certain lexicographical ranges and length constraints.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

These problems test your ability to optimize. Start with a brute force solution, then improve.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 16, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 29

❓

Frequently Asked Questions

What is the sliding window technique for string problems?

Sliding window maintains a "window" of characters with two pointers. Expand the right pointer to include characters, shrink from left when window violates constraints. Useful for substring problems, anagrams, and longest/shortest substring with properties.

Should I use top-down (memoization) or bottom-up (tabulation)?

Start with top-down (recursion + memoization) as it directly maps to the recursive thinking and handles only needed subproblems. Convert to bottom-up for better space efficiency and to avoid stack overflow. Bottom-up is often faster due to no recursion overhead.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Find All Good Strings"?

For this hard-level String problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?