Can't eliminate the evil strings from all strings between s1 and s2
I was able to find the number of string between s1 and s2 but can\'t think of a way to eliminate the evil strings.\n\nMy idea for finding all strings is as foll
I was able to find the number of string between s1 and s2 but can\'t think of a way to eliminate the evil strings.\n\nMy idea for finding all strings is as follows:\n\nAssume` s1 = \'ax\'` and `s2 = \'dc`\'.\nThe first characters are `\'a\'` and `\'d\'` respectively. From this, we can conclude that any strings that starts with `\'b\'` or` \'c\' `are surely going to be between `\'ax\' `and `\'dc\'`.\nSo, possible characters on first position = 2 i.e. `\'b\'` or` \'c\'`; and for the second position, there are 26 characters that are possible, so 26.\nHence `total strings = 2.26 = 52`.\nEssentially, we found the number of strings between `"ba"` and `"cz"` i.e.` ["ba", "cz"]`\n\nHowever, there are some strings that won\'t start with` \'b\' `or` \'c\' `but are still between `"ax"` and `"dc"` like `"db"` or` "ay"` and those are - `["ax", "az"]` and `["da, "dc"]`.\n1. `"ax" `to `"az"`\nAs first character for both is same, we can eliminate that directly only find strings between` "x" `and `"z"`. ---- > `3`\n2. `"da"` to `"dc"` == `"a"` to `"c"` ----> `3`\n\nIn general sense, we can convert any s1 to s2 range into  3 parts - \n1. Strings those start with same letter as first letter of s1.\n2. Strings those start with same letter as first letter of s2\n3. Strings that are in between.\n\nAnother example for easier understanding -\n`s1 = "pgdcv"`, `s2 = "uqpya"`\nPart 1 --> `["pgdcv", "pzzzz"]`\nPart 2 --> `["uaaaa", "uqpya"]`\nPart 3 --> `["qaaaa", "tzzzz"] `\nWe can easily find answer for Part 3 - First position can have any one of 4 `(q, r, s, t)` and remaining 4 have 26 possibilities, so `4.26.26.26.26 = 1,827,904`.\nFor Part 1 and Part 2, simply use recursion (delete first character).\nHint: Part 1 -->` ["pgdcv", "pzzzz"]` ==` ["gdcv", "zzzz"]` and Part 2 --> `["uaaaa", "uqpya"]` == `["aaaa", "qpya"].`\n\n-----\n\nHope you find this explanation helpful. Although this does not solve the given problem fully, it might still be helpful in solving other problems.\n\nIf anyone can build up on this and explain a way to eliminate evil strings, it will be very helpful.\n\n\nMy Partial Solution here:\n```\nclass Solution {\n \n    const long mod = 1000000007;\npublic:\n    long getTotalStrings(int n, string a, string b, int idx) {\n        \n        long answer = 0;\n        if (idx == n) {\n            return answer;\n        }\n        \n        // ----- Ignore the characters that are same in both strings\n        while (idx<n && a[idx] == b[idx]) {\n            idx++;\n        }\n        \n        if (idx == n) { \n            return 1; // strings were same and size of [X, X] is 1.\n        }\n        \n\t\t// ----- Part 3\n\t\t\n        long firstCharPoss = max(b[idx]-a[idx]-1, 0); \n        for (int i=idx+1; i<n; i++) { // for all remaining characters, 26 possibilities\n            firstCharPoss = (firstCharPoss*26)%mod;\n        }\n        answer  = (answer + firstCharPoss)%mod;\n        \n        // ----- Part 1\n        \n        string a_dash = a;\n        for (int i = idx+1; i<n; i++) {\n            a_dash[i] = \'z\';\n        }\n        answer = (answer + getTotalStrings(n, a, a_dash, idx+1))%mod;\n        \n        // ----- Part 2\n        \n        string b_dash = b;\n        for (int i = idx+1; i<n; i++) {\n            b_dash[i] = \'a\';\n        }\n        answer = (answer + getTotalStrings(n, b_dash, b, idx+1))%mod;\n        \n        // -----\n        \n        if (idx == n-1) {\n            if (a < b) answer = (answer + 2) %mod; // We want to also include string a and b\n            else if (a == b) answer = (answer + 1) %mod; // Both a and b are same, so only include once\n        }\n        \n        return answer%mod;\n    }\n    \n    long getEvilStrings(int n, string a, string b, string e) {\n        long answer = 0;\n        \n\t\t// TBD\n\t\t\n        return answer%mod;\n    }\n    \n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        long total = getTotalStrings(n, s1, s2, 0); \n        return (total + ((-getEvilStrings(n, s1, s2, evil))%mod))%mod;\n    }\n};\n```
[]