DP + BFS [ EXPLAINED]
IntuitionFigure out how many valid strings can be formed from the given words to match the target string. We try to break down the target by matching parts of i
# Intuition
Figure out how many valid strings can be formed from the given words to match the target string. We try to break down the target by matching parts of it using each word, calculating the longest possible match for each position of the target. We use the Knuth-Morris-Pratt (KMP) algorithm to help with efficient string matching and track the longest prefix-suffix using an array.

# Approach
We concatenate each word with the target, calculate the KMP table (LPS array), and for each position in the target, we check the maximum match length we can achieve using the words. We keep track of the number of jumps needed to cover the target.

# Complexity
- Time complexity:
O(n * m), where n is the number of words and m is the length of the target string. This is because we process each word and calculate its longest prefix-suffix array, which takes O(m) time per word.

- Space complexity:
O(n * (m + k)), where n is the number of words, m is the length of the target string, and k is the average length of the words. This is because we store the LPS arrays for each word combined with the target string.

# Code
```kotlin []
class Solution {
    // Function to calculate the minimum number of valid strings
    fun minValidStrings(words: Array<String>, target: String): Int {
        val targetLength = target.length
        val wordsCount = words.size
        val lpsArrayList = mutableListOf<IntArray>()

        // Process each word, compute its LPS (Longest Prefix Suffix) array
        for (word in words) {
            val combinedString = StringBuilder().apply {
                append(word)
                append('#')  // Separator between word and target
                append(target)
            }.toString()

            // LPS array will store the length of the longest prefix suffix at each index
            val lps = IntArray(word.length + targetLength + 1)
            kmp(lps, combinedString)  // Compute KMP (Knuth-Morris-Pratt) for the combined string
            lpsArrayList.add(lps)  // Add the LPS array to the list
        }

        var total = 0
        var i = targetLength - 1

        // Iterate over the target from the end and try to match substrings
        while (i >= 0) {
            var maxMatch = 0
            // For each word, find the maximum match length for the target
            for (j in 0 until wordsCount) {
                maxMatch = maxOf(maxMatch, lpsArrayList[j][words[j].length + 1 + i])
            }
            
            // If no match is found, return -1
            if (maxMatch == 0) return -1
            
            i -= maxMatch  // Move the target index backward by the matched length
            total++  // Increment the total number of valid strings
        }
        return total  // Return the total number of valid strings
    }

    // KMP algorithm to compute the LPS (Longest Prefix Suffix) array
    fun kmp(lps: IntArray, s: String) {
        var length = 0
        var i = 1

        // Traverse the string and build the LPS array
        while (i < s.length) {
            if (s[i] == s[length]) {
                length++
                lps[i] = length  // Store the length of the longest prefix suffix at index i
                i++
            } else {
                if (length != 0) {
                    // If mismatch happens, fall back to the last valid LPS length
                    length = lps[length - 1]
                } else {
                    lps[i] = 0  // No valid prefix-suffix match, set to 0
                    i++
                }
            }
        }
    }
}

```
['Array', 'Math', 'Binary Search', 'Dynamic Programming', 'Breadth-First Search', 'Segment Tree', 'Rolling Hash', 'String Matching', 'Hash Function', 'Kotlin']