Find all good strings problem in Data Structure

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

Java Approach Using HashMap

Output:

Code Explanation:

• This Java code implements a solution to find the number of good strings within a given range and avoid a specified evil string. It employs dynamic programming with memoization to efficiently explore all possible combinations. The findGoodStrings method initializes necessary data structures and starts the recursion.
• The f method handles the recursive exploration and memoization of subproblems. It iterates through all characters within the range for each position of the string, keeping track of evil string matches using a list of candidates.
• The generate method constructs strings of specified lengths with repeated characters. Finally, the main method takes user input for string lengths and bounds and then outputs the result.

Time Complexity:

• The time complexity of the findGoodStrings method is O2(n * m^2 * s^2), where n is the length of the string, m is the number of ciphers in the alphabet (26 in this instance), and s is the length of the evil string.
• The time complexity of the f method is O(n * m ^2), where n denotes the length of the string and m represents the number of characters in the alphabet.

Space Complexity:

• The space complexity is O(n * s ^2 * m), where n is the length of the string, s is the size of the alphabet, and m is the evil string length.

Drawback:

• However, given the high space complexity of this option, especially when dealing with huge inputs, there may be better choices of approach. By using a variable length array for memoizing intermediate results (memo) and another hashmap index (index) for storing indices, memory issues with regard to large inputs may arise.
• Moreover, a program with such an algorithm may experience stack overflow errors with fairly big values of the input strings, as each recursive call requires stack space. Thus, the solution serves as a base for the provided- Dynamic Programming tool to solve the problem more effectively.

Java Approach Using Dynamic Programming +KMP Algorithm

Output:

Code Explanation:

• This code calculates the count of "good strings" within the range defined by two strings, s1 and s2. A "good string" doesn't contain any substring matching an "evil string." It utilizes dynamic programming with memorization for optimization.
• The solve function recursively explores all possible character combinations within the given range, ensuring each string generated avoids containing any substring that matches the evil string.
• The Longest Prefix Suffix (LPS) array is computed for the evil string to optimize substring comparison.
• The solution efficiently handles character comparisons, considering the lower and upper bounds of each character position in the strings.

Time Complexity:

• The time complexity is O(n * m * k * l), in which n is the string length, m is the evil string length, k is the size of the alphabet, and l represents the number of recursive calls.

Space Complexity:

• Space complexity is O(n * k * k * m) which n is the string length and k is the alphabet size.