<p>You are given an array of strings <code>words</code> and a string <code>target</code>.</p>

<p>A string <code>x</code> is called <strong>valid</strong> if <code>x</code> is a <span data-keyword="string-prefix">prefix</span> of <strong>any</strong> string in <code>words</code>.</p>

<p>Return the <strong>minimum</strong> number of <strong>valid</strong> strings that can be <em>concatenated</em> to form <code>target</code>. If it is <strong>not</strong> possible to form <code>target</code>, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">words = [&quot;abc&quot;,&quot;aaaaa&quot;,&quot;bcdef&quot;], target = &quot;aabcdabc&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p>The target string can be formed by concatenating:</p>

<ul>
	<li>Prefix of length 2 of <code>words[1]</code>, i.e. <code>&quot;aa&quot;</code>.</li>
	<li>Prefix of length 3 of <code>words[2]</code>, i.e. <code>&quot;bcd&quot;</code>.</li>
	<li>Prefix of length 3 of <code>words[0]</code>, i.e. <code>&quot;abc&quot;</code>.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">words = [&quot;abababab&quot;,&quot;ab&quot;], target = &quot;ababaababa&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>

<p><strong>Explanation:</strong></p>

<p>The target string can be formed by concatenating:</p>

<ul>
	<li>Prefix of length 5 of <code>words[0]</code>, i.e. <code>&quot;ababa&quot;</code>.</li>
	<li>Prefix of length 5 of <code>words[0]</code>, i.e. <code>&quot;ababa&quot;</code>.</li>
</ul>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">words = [&quot;abcdef&quot;], target = &quot;xyz&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">-1</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 100</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 5 * 10<sup>4</sup></code></li>
	<li>The input is generated such that <code>sum(words[i].length) &lt;= 10<sup>5</sup></code>.</li>
	<li><code>words[i]</code> consists only of lowercase English letters.</li>
	<li><code>1 &lt;= target.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>target</code> consists only of lowercase English letters.</li>
</ul>

from typing import List
from collections import deque

class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        # Initialize trie components
        children = [[-1] * 26]  # children[node][char] = child_node_index
        fail = [0]               # fail[node] = failure_link_node_index
        output = [0]             # output[node] = maximum prefix length ending at this node

        # Function to insert a word's prefixes into the trie
        def insert(word: str):
            node = 0  # Start at root
            for i, char in enumerate(word, 1):
                c = ord(char) - ord('a')
                if children[node][c] == -1:
                    children[node][c] = len(children)
                    children.append([-1] * 26)
                    fail.append(0)
                    output.append(0)
                node = children[node][c]
                # Store the maximum prefix length at this node
                if i > output[node]:
                    output[node] = i

        # Insert all prefixes from all words
        for word in words:
            insert(word)

        # Build the failure links using BFS
        queue = deque()
        # Initialize the queue with depth 1 nodes
        for c in range(26):
            child = children[0][c]
            if child != -1:
                fail[child] = 0  # Failure link of depth 1 nodes is root
                queue.append(child)
            else:
                children[0][c] = 0  # Non-existing children point to root

        while queue:
            current = queue.popleft()
            for c in range(26):
                child = children[current][c]
                if child != -1:
                    # Find the failure link for the child
                    f = fail[current]
                    while children[f][c] == -1 and f != 0:
                        f = fail[f]
                    fail_child = children[f][c]
                    if fail_child == -1:
                        fail_child = 0
                    fail[child] = fail_child
                    # Update the output for the child node
                    if output[fail_child] > output[child]:
                        output[child] = output[fail_child]
                    queue.append(child)
                else:
                    # Set the child to follow the failure link
                    children[current][c] = children[fail[current]][c]

        n = len(target)
        dp = [float('inf')] * (n + 1)
        dp[0] = 0  # Base case: empty string requires 0 prefixes

        node = 0  # Start from the root of the automaton

        for i in range(n):
            c = ord(target[i]) - ord('a')
            # Traverse the automaton with the current character
            node = children[node][c]
            # If node is -1 (no transition), reset to root
            if node == -1:
                node = 0
            # Get the maximum prefix length ending at this node
            length = output[node]
            if length > 0:
                start_pos = i - length + 1
                if start_pos >= 0:
                    dp[i + 1] = min(dp[i + 1], dp[start_pos] + 1)

        return dp[n] if dp[n] != float('inf') else -1

41246