C++ Memoization + KMP Algorithm
IntuitionTo understand how to solve this problem, we are going to want to break it into separate components. The first is dp. Figuring out that this is a dp pro
# Intuition
To understand how to solve this problem, we are going to want to break it into separate components. The first is dp. Figuring out that this is a dp problem is intuition really, and it takes time solving problems to develop that. Some obvious indicators, though, are the constraints, indicating that we can use a more time-taking method.



# Approach
For my dp approach, I used memo, but tabulation works fine as well. There are 3 parameters which our recursive function will use: index, first, second, and third. I will go through these one by one to describe what they do.

# First parameter

This parameter has to do with the first condition for the string: That is, it must be greater than or equal to s1.This parameter essentially indicates if we can afford to take a character less than in the s1 string. Think about it like this: If we choose a character greater than s1 at the very beginning, then no matter what character we choose, the string will always be greater than s1. This is essentially what the first parameter is doing: If it is set to 0, then we have not yet chosen a character greater than s1, and therefore we must not choose one less. Similarly, if it is set to 1, then we can afford to choose any given character.

# Second Parameter

This parameter works essentially identical to the first one, except it tracks if we have picked a character less than s2 at any given index, so not much explanation is needed. I will give an example, though. Imagine this string:

s2 = "zjfft".

If we choose 'z' for our first character, then we will keep the second parameter at 0. This is because we can't afford to pick a character greater than s2 on the next run, as this would result in the string being greater.

If we instead chose 'm' for our first character, we would set it to 1, as no matter what we choose, the resultant string will ALWAYS be less than s2.

# Third Parameter

This is the most difficult parameter by far, as without it this problem would be medium difficulty. This parameter is essentially a string matching parameter: Think of it like the common variable j in two pointer techniques, keeping track of how many characters in a row we have. 

The difficult thing about this problem is that it is impossible to use the brute force string searching technique without making memoization impossible to implement. Therefore, we will have to use one of the optimal algorithms. 

The algorithm in question which we will implement is the KMP string matching algorithm. It is way too complex to explain here, so I advise you research it on your own before trying to understand this problem. Simply put, using this algorithm, we can efficiently search for the substring optimally, with the third parameter keeping track of where we are in the array.

# Complexity
- Time complexity:
O(n*m*2*2)=O(m*n)

- Space complexity:
O(m*n*2*2)=O(m*n)

# Code
```cpp []
class Solution {
public:

    int mod = pow(10,9)+7;

    vector<int> lps;

    int recur(int n, string& s1, string& s2, string& evil, int index,int first, int second, int third, vector<vector<vector<vector<int>>>>& dp) {
        if (index==n&&third!=evil.size()) {
            return 1;
        }

        if (index==n||third==evil.size()) {
            return 0;
        }

        if (dp[index][first][second][third]!=-1) {
            return dp[index][first][second][third];
        }

        int res = 0;

        int newThird = 0;


        for (int i = 0;i<26;i++) {
            if (second||((i<s2[index]-'a'))) {
                if ((i>s1[index]-'a')||first) {
                    if (i==evil[third]-'a') {
                        res+=recur(n,s1,s2,evil,index+1,1,1,third+1,dp);
                        res=res%mod;
                    } else {
                        newThird = third;
                        while (newThird>0&&i!=evil[newThird]-'a') {
                            newThird = lps[newThird-1];
                        }

                        if (i==evil[newThird]-'a') {
                            newThird++;
                        }
                        
                        res+=recur(n,s1,s2,evil,index+1,1,1,newThird,dp);
                        res=res%mod;
                    }
                    
                } else if (i==s1[index]-'a'){
                    if (i==evil[third]-'a') {
                        res+=recur(n,s1,s2,evil,index+1,first,1,third+1,dp);
                        res=res%mod;
                    } else {
                        newThird = third;
                        while (newThird>0&&i!=evil[newThird]-'a') {
                            newThird = lps[newThird-1];
                        }

                        if (i==evil[newThird]-'a') {
                            newThird++;
                        }
                        res+=recur(n,s1,s2,evil,index+1,first,1,newThird,dp);
                        res=res%mod;
                    }   
                    
                }
                
            } else if (i==s2[index]-'a') {
                if ((i>s1[index]-'a')||first) {
                    if (i==evil[third]-'a') {
                        res+=recur(n,s1,s2,evil,index+1,1,second,third+1,dp);
                        res=res%mod;
                    } else {
                        newThird = third;
                        while (newThird>0&&i!=evil[newThird]-'a') {
                            newThird = lps[newThird-1];
                        }

                        if (i==evil[newThird]-'a') {
                            newThird++;
                        }
                        res+=recur(n,s1,s2,evil,index+1,1,second,newThird,dp);
                        res=res%mod;
                    }
                    
                } else if (i==s1[index]-'a'){
                    if (i==evil[third]-'a') {
                        res+=recur(n,s1,s2,evil,index+1,first,second,third+1,dp);
                        res=res%mod;
                    } else {
                        newThird = third;
                        while (newThird>0&&i!=evil[newThird]-'a') {
                            newThird = lps[newThird-1];
                        }

                        if (i==evil[newThird]-'a') {
                            newThird++;
                        }
                        res+=recur(n,s1,s2,evil,index+1,first,second,newThird,dp);
                        res=res%mod;
                    }   
                    
                }
            }
        }

        return dp[index][first][second][third]=res;
    }

    int findGoodStrings(int n, string s1, string s2, string evil) {
        vector<vector<vector<vector<int>>>> dp(n+1,vector<vector<vector<int>>>(2,vector<vector<int>>(2,vector<int>(evil.size()+1,-1))));

        lps = vector<int>(evil.size(),0);

        int len = 0;

        for (int i = 1;i<evil.size();i++) {
            if (evil[i]==evil[len]) {
                lps[i]=++len;
            } else if (len>0) {
                while (evil[i]!=evil[len]&&len>0) {
                    len = lps[len-1];
                }

                if (evil[i]==evil[len]) {
                    lps[i] = ++len;
                }

                
            }
        }
        return recur(n,s1,s2,evil,0,0,0,0, dp)%mod;
    }
};
```
['String', 'Dynamic Programming', 'Memoization', 'String Matching', 'C++']