1397. Find All Good Strings

Description

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 109 + 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
• s1 <= s2
• 1 <= n <= 500
• 1 <= evil.length <= 50
• All strings consist of lowercase English letters.

 

Solutions

Solution: Dynamic Programming + KMP

• Time complexity: O(mn*26 -> mn)
• Space complexity: O(mn*2²+26m -> mn)
• m is evil.length

 

JavaScript

const findGoodStrings = function (n, s1, s2, evil) {
  const MODULO = 10 ** 9 + 7;
  const BASE_CODE = 'a'.charCodeAt(0);
  const evilLPS = getLPS(evil);
  const nextMatchedCount = Array.from({ length: evil.length }, () => new Array(26).fill(-1));
  const dp = Array.from({ length: n }, () => {
    return Array.from({ length: evil.length }, () => [
      [-1, -1],
      [-1, -1],
    ]);
  });

  const getCode = letter => letter.charCodeAt(0) - BASE_CODE;

  const getNextMatchedEvilCount = (code, matchCount) => {
    if (nextMatchedCount[matchCount][code] !== -1) {
      return nextMatchedCount[matchCount][code];
    }
    const letter = String.fromCharCode(code + BASE_CODE);

    while (matchCount && evil[matchCount] !== letter) {
      matchCount = evilLPS[matchCount - 1];
    }
    nextMatchedCount[matchCount][code] = evil[matchCount] === letter ? matchCount + 1 : matchCount;

    return nextMatchedCount[matchCount][code];
  };

  const findGoodCount = (index, matchedEvilCount, isPrefix1, isPrefix2) => {
    if (matchedEvilCount === evil.length) return 0;
    if (index === n) return 1;
    if (dp[index][matchedEvilCount][+isPrefix1][+isPrefix2] !== -1) {
      return dp[index][matchedEvilCount][+isPrefix1][+isPrefix2];
    }
    const code1 = getCode(s1[index]);
    const code2 = getCode(s2[index]);
    const minCode = isPrefix1 ? code1 : 0;
    const maxCode = isPrefix2 ? code2 : 25;
    let result = 0;

    for (let code = minCode; code <= maxCode; code++) {
      const nextMatchedEvilCount = getNextMatchedEvilCount(code, matchedEvilCount);
      const nextIsPrefix1 = isPrefix1 && code === code1;
      const nextIsPrefix2 = isPrefix2 && code === code2;

      result += findGoodCount(index + 1, nextMatchedEvilCount, nextIsPrefix1, nextIsPrefix2);
      result %= MODULO;
    }
    dp[index][matchedEvilCount][+isPrefix1][+isPrefix2] = result;

    return result;
  };

  return findGoodCount(0, 0, true, true);
};

function getLPS(pattern) {
  const n = pattern.length;
  const lps = Array.from({ length: n }, () => 0);
  let length = 0;

  for (let index = 1; index < n; index++) {
    while (length && pattern[index] !== pattern[length]) {
      length = lps[length - 1];
    }
    if (pattern[index] === pattern[length]) {
      length += 1;
    }
    lps[index] = length;
  }
  return lps;
}