Digit dp solution c++
Since there are lower bound and upper bound, the common way is f(l, m) = f(0, m) - f(0, l-1). we can compute the number of strings which are smaller than s and 
Since there are lower bound and upper bound, the common way is f(l, m) = f(0, m) - f(0, l-1). we can compute the number of strings which are smaller than s and no \'evil\' string.\n\ntrans[i][j] is the maximum matched characters after add (j + \'a\') at the position (i + 1) in the \'evil\' string.\n\ndp[i][j][k] is the prefix [0, i) of generated string has matched [0, j] of \'evil\' string. k = 0 if generated string is greater than s and k = 1 otherwise.. \n\nbase case: dp[0][0][1] = 1, in this case, the only one is empty string.\nanswer is the sum of number of strings matched all the prefixes of \'evil\' string except itself.\n```\nconst int P = 1e9 + 7;\n//long long dp[501][51][2];\n//int trans[51][26];\nclass Solution {\npublic:\n    long long dp[501][51][2];\n    int trans[51][26]; //array declaration should be in the class\n    long long calc(int n, string s, string evil) {\n        int e_s = evil.size();\n        for (int i = 0; i < e_s; i++) {\n            string f = evil.substr(0, i);\n            for (int j = 0; j < 26; j++) {\n                string g = f + (char)(j + \'a\');\n                //int flag = 1;\n                for (int k = 0; k <= i; k++) {\n                    if (g.substr(k) == evil.substr(0, i + 1 - k)) {\n                        trans[i][j] = i + 1 - k;\n                        //flag = 0;\n                        break;\n                    }\n                }\n            }\n        }\n        for (int i = 0; i <= n; i++) {\n            for (int j = 0; j < e_s; j++) {\n                dp[i][j][0] = dp[i][j][1] = 0;\n            }\n        }\n        dp[0][0][1] = 1;\n        for (int i = 1; i <= n; i++) {\n            for (int j = 0; j < e_s; j++) {\n                for (int k = 0; k < 26; k++) {\n                    for (int l: {0, 1}) {\n                        int tl;\n                        if (k < s[i - 1] - \'a\')  tl = 1;\n                        else if (k > s[i - 1] - \'a\')  tl = 0;\n                        else  tl = l;\n                        (dp[i][trans[j][k]][l] += dp[i - 1][j][tl]) %= P;\n                    }\n                }\n            }\n        }      \n        long long ans = 0;\n        for (int i = 0; i < e_s; i++) {\n            (ans += dp[n][i][1]) %= P;\n        }\n        return ans;        \n    }\n    long long findGoodStrings(int n, string s1, string s2, string evil) {\n        long long ans = calc(n, s2, evil);\n        int ok = 1;\n        for (int i = 0; i < s1.size() and ok; i++) {\n            ok = s1[i] == \'a\';\n        }\n        if (!ok) {\n            for (int j = (int)s1.size() - 1; j >= 0; j--) {\n                if (s1[j] > \'a\') {\n                    s1[j]--;\n                    break;\n                }\n                s1[j] = \'z\';\n            }\n            ((ans += P) -= calc(n, s1, evil)) %= P;\n        }\n        return ans;\n    }\n};
[]