java digitDp + KMP with explanation
Basic Concept:\nAnswer = the number of strings which are less or equal than S2 -  the number of strings which are less or equal than S1-1.\n\nState:\ndp[i][stat
**Basic Concept:**\nAnswer = the number of strings which are less or equal than S2 -  the number of strings which are less or equal than **S1-1**.\n\n**State:**\ndp[i][state][0/1] means first i characters at matching state, 0 means less than, 1 means equal.\n\nstate means number of matching characters in first i charater in string S with evil.\n\n**Initialization:**\ndp[0][0][1] = 1, because first 0 character in S is "", matching 0 charater in evil, we only have it equal, in this state there is string less than "".\n\n**State Transformation:**\nwhen we add new character to current state:\nwe update dp array based upon less or equal, so two scenarios.\n\n1. less than - dp[i][state][0]\nif we are looking for less than state, than it can come from a previous less than state, the charater we are adding can be anyone from \'a\'-\'z\'.\n```\n  for(char c=\'a\'; c<=\'z\'; c++){\n\t  int nextstate = getNextState(state, c, e);\n\t  dp[i+1][nextstate][0] = (dp[i+1][nextstate][0] + dp[i][state][0])%mod;\n  }\n```\nAlso, it can come from a previous equal state, but now, we can only add characters which is less than S.charAt(i).\n\t\n\tfor (char c = \'a\'; c < s[i]; c++) {\n\t\tint nextstate = getNextState(state, c, evil);\n\t\tdp[i+1][nextstate][0] = (dp[i+1][nextstate][0] + dp[i][state][1]) % mod;\n\t}\n\t\n2. equal - dp[i][state][1]\nTo get the equal state, it has to come from a previous equal state and the only character we can add is S.charAt(i) itself.\n```\n\tint nextstate = getNextState(state, s.charAt(i), e);\n\tdp[i+1][nextstate][1] = (dp[i+1][nextstate][1] + dp[i][state][1])%mod;\n```\n**How do we update state?**\nWe have a getNextState method which is utilizing **Next[]** in KMP, so we can easily find next state.\n\n```\nclass Solution {\n    int mod = 1_000_000_007;\n    int[] next;\n    public int findGoodStrings(int n, String s1, String s2, String evil) {\n        //s1--\n        char[] s1arr = s1.toCharArray();\n        for(int i=s1.length()-1; i>=0; i--){\n            if(s1arr[i] > \'a\'){\n                s1arr[i] = (char)(s1arr[i]-1);\n                break;\n            }else\n                s1arr[i] = \'z\';\n        }\n        s1 = new String(s1arr);\n        next = getNext(evil);\n        if(s1.compareTo(s2)>0)\n            return lessOrEqualThan(s2, evil);\n        return (lessOrEqualThan(s2, evil)-lessOrEqualThan(s1, evil)+mod)%mod;\n    }\n    public int lessOrEqualThan(String s, String e){\n        long[][][] dp = new long[s.length()+1][e.length()+1][2];\n        dp[0][0][1] = 1;\n        long res = 0;\n        for(int i=0; i<s.length(); i++){\n            for(int state=0; state<e.length(); state++){\n                for(char c=\'a\'; c<=\'z\'; c++){\n                    int nextstate = getNextState(state, c, e);\n                    dp[i+1][nextstate][0] = (dp[i+1][nextstate][0] + dp[i][state][0])%mod;\n                }\n                for(char c=\'a\'; c<s.charAt(i); c++){\n                    int nextstate = getNextState(state, c, e);\n                    dp[i+1][nextstate][0] = (dp[i+1][nextstate][0] + dp[i][state][1])%mod;\n                }\n                int nextstate = getNextState(state, s.charAt(i), e);\n                dp[i+1][nextstate][1] = (dp[i+1][nextstate][1] + dp[i][state][1])%mod;\n            }\n        }\n        for(int i=0; i<e.length(); i++){\n            res = (res + dp[s.length()][i][0])%mod;\n            res = (res + dp[s.length()][i][1])%mod;\n        }\n        return (int)res;\n    }\n    public int getNextState(int prevState, char nextChar, String evil){\n        int idx = prevState;\n        while(idx!=-1 && evil.charAt(idx) != nextChar)\n            idx = next[idx];\n        return idx+1;\n    }\n    public int[] getNext(String e){\n        int len = e.length();\n        int[] next = new int[len];\n        next[0] = -1;\n        int last = -1;\n        int i = 0;\n        while(i < len-1){\n            if(last==-1 || e.charAt(i)==e.charAt(last)){\n                i++;\n                last++;\n                next[i] = last;\n            }else\n                last = next[last];\n        }\n        return next;\n    }\n}
[]