<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>3</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>3</sup></code></li>
	<li><code>target</code> consists only of lowercase English letters.</li>
</ul>

class StringHashing:

    def __init__(self, s):
        self.BASE, self.MOD = 972137871, 9726637411273
        res = self.calculate_hash(s)
        self.hash_table, self.pol = self.calculate_hash(s)
            
    def calculate_hash(self, s):
        N = len(s)
        hash_table = [0] * N
        pol = [1] * N
        
        hash_table[0] = ord(s[0])
        for i in range (1, N):
            hash_table[i] = (hash_table[i - 1] * self.BASE + ord(s[i])) % self.MOD
            pol[i] = (pol[i - 1] * self.BASE) % self.MOD
        return [hash_table, pol]
            
    def get_hash(self, start, end):
        if start == 0:
            return self.hash_table[end]
        else:
            return (self.hash_table[end] - self.hash_table[start - 1] * self.pol[end - start + 1]) % self.MOD

        
class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        """
        Let try some initial observations:
        1. What if we can answer all queries:
            + isPrefix(target[i:j]) ? True : False with an acceptable complexity ( Need define, maybe <= O(log) )
            
        2. Any Greedy idea?
            + If we consider from end of target back -> Longer prefix is better. 
            "x1...abcdef": bcdef is a prefix, abc is a prefix -> 2
        
        """
        
        def get_longest_prefix(start):
            if string_hashing.get_hash(start, start) not in prefix_hash_table:
                return -1
            lower = start
            upper = n - 1
            while lower < upper:
                mid = (lower + upper + 1) // 2
                hash_value = string_hashing.get_hash(start, mid)
                if hash_value in prefix_hash_table:
                    lower = mid
                else:
                    upper = mid - 1
            return lower
        
        n = len(target)
        output = 0
        string_hashing = StringHashing(target)
        prefix_hash_table = set()
        heap = []
        
        for word in words:
            hash_table, _ = string_hashing.calculate_hash(word)
            for hash_value in hash_table:
                prefix_hash_table.add(hash_value)
        
        for i in range(n):
            j = get_longest_prefix(i)
            if j != -1:
                heappush(heap, [-j, i])
            
        # print(heap)
        
        curr_pos = n - 1
        while curr_pos >= 0:
            next_pos = curr_pos
            flag = False
            if not heap or abs(heap[0][0]) < curr_pos:
                return -1
            while heap and abs(heap[0][0]) >= curr_pos:
                neg_j, i = heappop(heap)
                if i <= curr_pos:
                    flag = True
                next_pos = min(next_pos, i)
            curr_pos = next_pos - 1
            
            if not flag:
                return -1
            output += 1
            
        return output
22420