Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1397.html

1397. Find All Good Strings (Hard)

Given the strings s1 and s2 of size n, and the string evil. Return the number of good strings.

A good string has size n, it is alphabetically greater than or equal to s1, it is alphabetically smaller than or equal to s2, and it does not contain the string evil as a substring. Since the answer can be a huge number, return this modulo 10^9 + 7.

 

Example 1:

Input: n = 2, s1 = "aa", s2 = "da", evil = "b"
Output: 51 
Explanation: There are 25 good strings starting with 'a': "aa","ac","ad",...,"az". Then there are 25 good strings starting with 'c': "ca","cc","cd",...,"cz" and finally there is one good string starting with 'd': "da". 

Example 2:

Input: n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet"
Output: 0 
Explanation: All strings greater than or equal to s1 and smaller than or equal to s2 start with the prefix "leet", therefore, there is not any good string.

Example 3:

Input: n = 2, s1 = "gx", s2 = "gz", evil = "x"
Output: 2

 

Constraints:

  • s1.length == n
  • s2.length == n
  • 1 <= n <= 500
  • 1 <= evil.length <= 50
  • All strings consist of lowercase English letters.

Related Topics:
Dynamic Programming

Solution 1.

Let dp[i][j][k]

Let tr[i][j] be the maximum suffix length if we prepend character 'a' + j to a e’s suffix of size i.

For example, if e = "abab", i = 2, j = 1, so the new suffix we get by prepending 'a' + 1 = 'b' to e[0..(i-1)] = "ab" is "bab", and "bab" is a suffix of e that is of size 3. So tr[2][1] = 3.

https://www.youtube.com/watch?v=uqdsHJzlsIc Digit DP: https://codeforces.com/blog/entry/53960



  • class Solution {
    public int findGoodStrings(int n, String s1, String s2, String evil) {
        int length = evil.length();
        int[][][] dp = new int[n][length][4];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < length; j++) {
                for (int k = 0; k < 4; k++)
                    dp[i][j][k] = -1;
            }
        }
        int[][] transfers = new int[length][26];
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < 26; j++)
                transfers[i][j] = -1;
        }
        int[] fails = new int[length];
        for (int i = 1; i < length; i++) {
            int state = fails[i - 1];
            while (state > 0 && evil.charAt(state) != evil.charAt(i))
                state = fails[state - 1];
            if (evil.charAt(state) == evil.charAt(i))
                fails[i] = state + 1;
        }
        return depthFirstSearch(n, s1, s2, evil, dp, transfers, fails, 0, 0, 3);
    }

    public int depthFirstSearch(int n, String s1, String s2, String evil, int[][][] dp, int[][] transfers, int[] fails, int index, int state, int bound) {
        final int MODULO = 1000000007;
        int length = evil.length();
        if (state == length)
            return 0;
        if (index == n)
            return 1;
        if (dp[index][state][bound] >= 0)
            return dp[index][state][bound];
        dp[index][state][bound] = 0;
        char low = ((bound & 1) > 0) ? s1.charAt(index) : 'a';
        char high = ((bound & 2) > 0) ? s2.charAt(index) : 'z';
        for (char c = low; c <= high; c++) {
            int nextState = getTransfer(evil, transfers, fails, state, c);
            int nextBound = 0;
            if ((bound & 1) > 0 && c == s1.charAt(index))
                nextBound++;
            if ((bound & 2) > 0 && c == s2.charAt(index))
                nextBound += 2;
            dp[index][state][bound] = (dp[index][state][bound] + depthFirstSearch(n, s1, s2, evil, dp, transfers, fails, index + 1, nextState, nextBound)) % MODULO;
        }
        return dp[index][state][bound];
    }

    public int getTransfer(String evil, int[][] transfers, int[] fails, int state, char letter) {
        int letterIndex = letter - 'a';
        if (transfers[state][letterIndex] >= 0)
            return transfers[state][letterIndex];
        while (state > 0 && evil.charAt(state) != letter)
            state = fails[state - 1];
        int transfer = evil.charAt(state) == letter ? state + 1 : 0;
        transfers[state][letterIndex] = transfer;
        return transfer;
    }
}

  •

All Problems

All Solutions