We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find All Good Strings

Difficulty: Hard

Problem 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 10^9 + 7.

Key Insights

  • The problem requires generating all strings of length n that lie between s1 and s2 and do not contain the substring evil.
  • A dynamic programming approach can be used to efficiently count the valid strings without generating them explicitly.
  • The key states in the DP table will keep track of the current position, whether the current string is still bounded by s1 or s2, and the length of the matching prefix of evil.

Space and Time Complexity

Time Complexity: O(n * m * 2) where n is the length of the strings and m is the length of the evil string.
Space Complexity: O(n * m * 2) for the DP table.

Solution

The solution utilizes dynamic programming along with a finite automaton for string matching. The idea is to maintain a DP table where dp[pos][is_prefix1][is_prefix2][evil_length] represents the number of valid strings that can be formed starting from position pos, where is_prefix1 indicates the string is still bound by s1, is_prefix2 indicates it is still bound by s2, and evil_length tracks how many characters of evil match the current string.

  1. Initialize a DP table with all values set to zero.
  2. Iterate through each position of the string from 0 to n.
  3. For each position, consider each character from 'a' to 'z' and update the DP values based on whether the character can still maintain the bounds with s1 and s2, and how it affects the matching of evil.
  4. Finally, sum up all valid configurations from the last position.

Code Solutions

def findGoodStrings(n, s1, s2, evil):
    MOD = 10**9 + 7
    m = len(evil)
    dp = [[[-1 for _ in range(m)] for _ in range(2)] for _ in range(2)]
    
    def dfs(pos, is_prefix1, is_prefix2, evil_length):
        if evil_length == m:  # If we matched the whole evil string
            return 0
        if pos == n:  # If we reached the end of the string
            return 1
        
        if dp[is_prefix1][is_prefix2][evil_length] != -1:
            return dp[is_prefix1][is_prefix2][evil_length]
        
        total = 0
        lower_bound = s1[pos] if is_prefix1 else 'a'
        upper_bound = s2[pos] if is_prefix2 else 'z'
        
        for char in range(ord(lower_bound), ord(upper_bound) + 1):
            next_is_prefix1 = is_prefix1 and (char == ord(lower_bound))
            next_is_prefix2 = is_prefix2 and (char == ord(upper_bound))
            next_evil_length = evil_length
            
            while next_evil_length > 0 and chr(char) != evil[next_evil_length]:
                next_evil_length -= 1

            if chr(char) == evil[next_evil_length]:
                next_evil_length += 1
                
            total += dfs(pos + 1, next_is_prefix1, next_is_prefix2, next_evil_length)
            total %= MOD
        
        dp[is_prefix1][is_prefix2][evil_length] = total
        return total
    
    return dfs(0, True, True, 0)
← Back to All Questions