Introduction

In this blog post, we will explore how to solve the LeetCode problem "1397" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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.

Explanation

Here's the breakdown of the solution and the Python code:

• High-Level Approach:

  • Dynamic Programming with KMP: Use dynamic programming to count the number of valid strings. The KMP algorithm is used to efficiently track occurrences of the evil string as we build potential good strings.
  • State Definition: The DP state includes the current length of the string being built, the current state of the KMP automaton (how much of evil has been matched), and boolean flags indicating whether we are still within the bounds of s1 and s2.
  • Transitions: Iterate through all possible characters ('a' to 'z') and update the DP state. The KMP automaton state is updated based on the chosen character. The bound flags are updated based on whether the chosen character stays within the lexicographical constraints of s1 and s2.

• Complexity:

  • Time Complexity: O(n m 26), where n is the length of s1 and s2, and m is the length of evil.
  • Space Complexity: O(n * m)

Code

    def solve():
    n, s1, s2, evil = int(input()), input(), input(), input()

    MOD = 10**9 + 7

    def compute_lps(evil):
        m = len(evil)
        lps = [0] * m
        length = 0
        i = 1
        while i < m:
            if evil[i] == evil[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        return lps

    lps = compute_lps(evil)
    m = len(evil)

    dp = {}

    def calculate(index, kmp_state, less, greater):
        if kmp_state == m:
            return 0
        if index == n:
            return 1

        if (index, kmp_state, less, greater) in dp:
            return dp[(index, kmp_state, less, greater)]

        ans = 0
        start = 'a' if greater else s1[index]
        end = 'z' if less else s2[index]

        for char_code in range(ord(start), ord(end) + 1):
            char = chr(char_code)
            next_kmp_state = kmp_state
            while next_kmp_state > 0 and char != evil[next_kmp_state]:
                next_kmp_state = lps[next_kmp_state - 1]
            if char == evil[next_kmp_state]:
                next_kmp_state += 1

            next_less = less or (char < s2[index])
            next_greater = greater or (char > s1[index])

            ans = (ans + calculate(index + 1, next_kmp_state, next_less, next_greater)) % MOD

        dp[(index, kmp_state, less, greater)] = ans
        return ans

    print(calculate(0, 0, False, False))

solve()