What's wrong with this DP ( 51/53 passed, WA, O(m*n) ) ?
Could anyone please help me? Thank you in advance !\n\n\nFor the Wrong Answer case, the input is:\n\n24\n"bqdkyblcurkzakgssmqlilwy"\n"uaklruspcoqrfleedknktbcu"\
Could anyone please help me? Thank you in advance !\n\n\nFor the Wrong Answer case, the input is:\n```\n24\n"bqdkyblcurkzakgssmqlilwy"\n"uaklruspcoqrfleedknktbcu"\n"ziymrjsz"\n```\n\nMy output is `470060983` and expected answer is `19674812`.\n\n\n```python\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        dp = [ (True, True, 1) ] * n\n        m = len(evil)\n        M = int(1e9+7)\n\n        start = 0\n        while start < n and s1[start] == s2[start]: start += 1\n        if evil in s1[:start]: return 0    \n        if start == n: return 1\n\n        start_cnt = ord( s2[start] ) - ord( s1[start] ) - 1\n        start_include1, start_include2 = True, True\n        if s1[ max(0, start-m+1) : start ] == evil[:m-1]:\n            if s1[start] == evil[-1]: start_include1 = False\n            elif s2[start] == evil[-1]: start_include2 = False\n            elif s1[start] < evil[-1] < s2[start]: start_cnt -= 1   \n        dp[start] = ( start_include1, start_include2, start_cnt )\n\n\n        for index in range(start+1, min(start+m, n) ):\n            include1, include2, cnt = dp[index-1]\n\n            new_include1 = include1 and s1[ max(0, index-m+1) : index+1] != evil\n            new_include2 = include2 and s2[ max(0, index-m+1) : index+1] != evil\n\n            new_cnt = cnt*26 % M + include1 * (ord(\'z\') - ord(s1[index])) + include2 * (ord(s2[index]) - ord(\'a\')) \n            if index >= m-1:\n                lprefix = start - index + m - 1\n                if s1[index-m+1 : start] == evil[ : lprefix ]:\n                    if s1[ start : index+1 ] < evil[lprefix : ] < s2[ start : index+1 ]:\n                        new_cnt -= 1\n\n            dp[index] = ( new_include1, new_include2, new_cnt % M )\n\n\n        for index in range( min(start+m, n), n):\n            include1, include2, cnt = dp[index-1]\n            prev_include1, prev_include2, prev_cnt = dp[index-m]            \n\n            new_include1 = include1 and s1[ index-m+1 : index+1] != evil\n            new_include2 = include2 and s2[ index-m+1 : index+1] != evil\n\n            new_cnt = cnt*26 % M + include1 * (ord(\'z\') - ord(s1[index])) + include2 * (ord(s2[index]) - ord(\'a\')) - prev_cnt            \n            if prev_include1 and s1[ index-m+1 : index+1] < evil:\n                new_cnt -= 1\n            if prev_include2 and s2[ index-m+1 : index+1] > evil:\n                new_cnt -= 1\n\n            dp[index] = ( new_include1, new_include2, new_cnt % M )\n\n\n        return sum( dp[-1] ) % M \n```
[]