Rolling hash + sliding window + DP: $O(n+\sum l_i)$ solution (With rigorous correctness proof)
Intuition and Approachn,∑li​ in title refers to the length of target and the total length of all words in words respectively.Approach 1: Using trie + dynamic pr
# Intuition and Approach
<!-- Describe your first thoughts on how to solve this problem. -->
$n,\sum l_i$ in title refers to the length of `target` and the total length of all words in words respectively.

## Approach 1: Using trie + dynamic programming (Correct but inefficient )

I had not looked at hint or even the topics before I started this approach. I knew it wouldn't be efficient enough but it was my solution. A fairly straight forward method. 

1. Build a trie using all words in `words`. 

2. INITIALIZE `min_valid_prefix` where `min_valid_prefix[i]` should hold the minimum number of valid prefixes that can be concatenated to form `target[0...i]` i.e `i+1` length prefix of target

3. FOR `i` from 0 to length of `target`-1
4. IF `i-1` has not been updated, it means there is no way to build `target[0..i-1]` with valid prefixes. return -1 immediately
5. OTHERWISE, ASSIGN `j`=`i`

6. Start at the root of trie

7. WHILE `j` < length of `target` AND we are in a valid node of trie
8. MOVE to `target[j]` in trie if `target[j]` is  a child of current node and update `min_valid_prefix[j]` to the minimum of  `min_valid_prefix[j]` and (`min_valid_prefix[i-1] + 1` or 1 if `i` is 0) OTHERWISE break out of WHILE. 
9. INCREMENT `j`
10. END WHILE
   
11. END FOR `i`

Time complexity is $O(nl)$ where $n$ is the length of target and $l$ is the length of longest word in `words` in worst case

I knew I would get TLE but I could build a reasonably efficient algorithm that works correctly without even looking at the topic.

At this point, I decided to take a look at the topics. I saw rolling hash. I had done rolling hash before but it never crossed my mind to use it for this problem before. It was when I thought maybe I could solve it using rolling hash + sliding window + DP. Never looked at the hint until I completed it.

## Approach 2: Rolling hash + DP + sliding window:
Rolling hash algorith
Assign a=1, b=2 and so on....
rolling for string $s = c_1c_2c_3..c_n$ 
is $c_1 * 27^{n-1} + c_2 * 27^{n-2}..+ c_n * 27^0$ reduced module $m$ where $m$ is some prime number. To minimize chances of a hash collision i.e. a substring in `target` that has the same hash as some valid prefix in `words` but are not the same, I used three different rolling hashes, calculated the same way, but with three different modulo, specifically Mersenne primes $2^{19}-1$, $2^{31}-1$, $2^{61}-1$ but for simplicity I pretend I used only one for pseudocode


ALGORITHM:
1. BUILD a hash set of rolling hashes using all prefixes of all words in `words`. It can be done efficiently with $O(\sum l_i)$ where $l_i$ is the length of `word[i]`. Lookup and addition can be done in $O(1)$ amortized time
2. PRECALCULATE $27^i$ reduced modulo a prime $m$ for all $0\le i \le l$ where $l$ is the length of longest word
3. INITIALIZE `min_valid_prefix` which has the same meaning as in my previous approach
4. INITIALIZE `i` to 0
5. INITIALIZE `window_rolling_hash` to 0
6. FOR `j` in `0` to length of `target` - 1
7. UPDATE `window_rolling_hash` by adding  `target[j]` to current window
8. WHILE `window_rolling_hash` IS NOT in the set of rolling hashes and `i` $\le$ `j`
9. UPDATE `window_rolling_hash` to remove `target[i]` from current window and increment `i`. For quick substraction use precalculated $27^{j-i}$ from 2.
10. END WHILE 
11. IF `i` goes beyond `j` there is no way to form `target[0..j]` using valid prefixes so entire `target` can also not be built like that. RETURN -1 immediately
12. OTHERWISE SET `min_valid_prefix[j] = 1 + min_valid_prefix[i-1]` OR 1 if `i` is 0
13. END FOR
14. RETURN the last value in `min_valid_prefix`

Unlike our previous approach, here we do not consider all possible sub-strings, so we could still be skeptical that it gives the correct answer. It is not immediately clearly why this algorithm is correct. So let's go for a rigorous proof that this algorithm is correct. For simplicity of proof, we assume that no collision can occur.

We can see that we advance $j$ as long as current window is a valid prefix. We advance $i$ when our current window is not a valid prefix

Define $O_0 = 0$ for initialization.
Recursive equation , $O_i = MIN_{l=0}^{i-1}{O_l} + 1$ for $i > 0$


### Lemma 1: Suppose that $O_n$ be the minimum number of valid strings to form $n$ length valid prefix of  `target`. Then $O_{i+1} \ge O_i$ for all $i$
For simplicity, we ignore the scenario where a `target` cannot be constructed using valid strings which is an undefined case.
suppose we have some $i$ such that $O_{i+1} < O_i$
$O_{i}$

$O_i = 1$ if `target[0..i-1]` is a valid prefix which is the smallest it can be so `target[0..i-1]` cannot be a valid prefix itself.


Because, $O_{i+1} < O_i$, it's optimal value could not be $O_{i+1} = O_i + 1$. Therefore optimal value is $O_{i+1} = O_l + 1$ for some $0 \le l < i$.

Any prefix of a valid prefix is also a valid prefix, so if `target[l..i]` is a valid prefix then so is `target[l..l]`, `target[l..l+1]` and so on. Therefore `target[l..i]` is also a valid prefix. Since, $l < i$, and `target[l..i]` is a valid prefix, it must have ben considered in computation of $O_i$. Therefore, $O_i \le O_l + 1 = O_{i+1}$ which is a contradiction.

### Lemma 2: Array `min_valid_prefix` is non-decreasing
PROOF:
`min_valid_prefix[i]` holds $O_{i+1}$. Since, $O$ is a non-decreasing sequence, array `min_valid_prefix` must also be non-decreasing during the execution. Let's prove this as step 1.

Again, let's assume that `target` cn really be constructed using valid strings.
Therefore, `min_valid_prefix[0]` is always 1 because when `j=0` and `target[0..0]` is a valid substring, `i` must also be 0. This is because $i$ must be less than or equal to $j$, and $i$ goes beyond $j$ we return -1 immediately. 

Likewise `min_valid_prefix[1]` is either 1 or 2 because $i$ is either 0 or 1 when $j=1$. Since `min_valid_prefix[1]` is greater than or equal to `min_valid_prefix[0]`,we have established a base condition. Suppose that `min_valid_prefix[i]` $\ge$ `min_valid_prefix[i-1]` holds for all $i \le k$. 

Consider the course of execution of program when $j=k+1$. Suppose value of $i$ at that point of execution is $l$ where `target[l..k+1]` is valid string. At that point, the program assigns `min_valid_prefix[l-1] + 1` (OR just `1` if $l=0$). Before that point, the program should  have also reached $j=k$. Suppose that the value of $i$ at the point of execution is $l'$ such that `target[l'...k]` is a valid string. Program  assigns `min_valid_prefix[k] = min_valid_prefix[l'-1] + 1` (OR just `1`) Here, $0\le l \le k+1$ Therefore $l-1 \le k$. Since, $i$ never decreases, and $i=l'$ is reached before $i=l$, we can conclude that $l' \le l$. Putting it together, $l'-1 \le l-1 \le k$. By prior assumption, we have `min_valid_prefix[l'-1] + 1` $\le$ `min_valid_prefix[l-1] + 1`. Therefore, `min_valid_prefix[k]` $\le$ `min_valid_prefix[k +1]`. 

PROVED BY INDUCTION


### Lemma 3: Suppose that `target[i..j]` which is a valid prefix found in current window during program execution. Then, there exists no $i' < i$ such that `target[i'..j]` is a valid prefix

Proof:
SUPPOSE that such an $i'$ exists. Then `target[i'..j']` is a valid prefix for all $i' \le j' \le j$
During the course of execution of program, we would return immediately if $i'$ went past the value of $j$. Suppose that the value of $j$ when $i$ becomes $i'$ is $j'$. Since, $i'$ could not have gone beyond $j'$, we can conclude that $i' \le j' \le j$. 
As we have established that `target[i'..j']` is a valid prefix, the program will to advance $j$ for next iteration. Because, `target[i'..j'']` is a valid prefix for all $j' \le j'' \le j$, we never advance $i$ until we reach $j$ in current window. Since the current window is still a valid prefix, we advance $j$ to $j+1$. Therefore, the window `target[i..j]` would never be encountered during the execution of program which contradicts our assumption.

### Lemma 4: Suppose that `target[i..j]` in current window is a valid prefix. We update `min_valid_prefix[j]` as  `min_valid_prefix[i-1] + 1` before advancing $i$. This `min_valid_prefix[j]` is the optimal value

Proof:
We have already established that no $i' < i$ exists such that `target[i'..j]` is a valid prefix. suppose that there exists $i' > i$ such that `target[i'..j]`. We never consider such $i'$ during the execution. However since `min_valid` is non-decreasing `min_valid_prefix[i'-1]` $\ge$ `min_valid_prefix[i-1]`. If `i` is 0, then `min_valid_prefix[j]` is 1 which is the most optimal. And for every $i' > i$, `min_valid_prefix[i'-1] + 1` $\ge$ `min_valid[i'] + 1` so we do not need to consider such $i'$.



Proving these three lemmas proves that our sliding window + rolling hash + DP approach gives the optimal answer. 


Final Note: Unmatching rolling hash can rule out an answer but the converse is not true. For this approach, we do not verify that the subtring is actually correct for a rolling hash match, otherwise it would still cause TLE in many custom made test cases. 









# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O(n + \sum l_i)$ where $l_i$ is the length of each word

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(n + \sum l_i)$.  DP table and the set of rolling hashes

# Code
```python3 []
class Solution:

    


    def minValidStrings(self, words: List[str], target: str) -> int:
    

    # # A less efficient approach using dynamic programming, (only one I can think of right now)
    # # with complexity O(m * n) where n is len(target) and m is the length of longest word in words

    #     for i in range(len(target)):
    #         # To start from i, we should be able to form target[0..i-1] with valid concatenations
    #         # if it is impossible to form any prefix of target that way it is impossible to form
    #         # target that way
    #         if i == 0 or min_valid[i-1] != -1:
    #             start = root
    #             j = i
    #             while j < len(target) and start is not None:
    #                 start = start.get_child(target[j])
    #                 if start is not None:
    #                     # prefix found
    #                     n_valid_suggest = 1 if i==0 else min_valid[i-1] + 1
    #                     if min_valid[j] == -1 or min_valid[j] > n_valid_suggest:
    #                         min_valid[j] = n_valid_suggest
    #                 j += 1
    #             #print(min_valid)
    #         else:
    #             return -1

    #     return min_valid[-1]

    # Attempt 2 using rolling hash, I haven'r checked hint yet

    # Assume that ho rolling hash collision will ever occur.
    # I will use it modulo a 64 bit prime number

    # check the length of longest word in words
        l_l = max([len(word) for word in words])
        # I will use 3 different modulo (3 mersenne primes) 
        # to calculate 3 different rolling hashes all within 64 bit
        modulos = (int(pow(2, 19)-1), int(pow(2, 31)-1) , int(pow(2, 61)-1)) 


        # precalculate 27^l for l from 1 to l_1
        powers_27 = [None]*(l_l + 1)
        powers_27[0] = (1,1,1)
        for i in range(1, l_l + 1):
            (p1, p2, p3) = powers_27[i-1]
            (m1,m2,m3) = modulos
            powers_27[i] = ((p1*27)%m1, (p2*27)%m2, (p3*27)%m3)

        # build a set to add every prefix in words. I will calculate 4 rolling hashes
        # for 4 different modulo
        rolling_hashes = set()
        for word in words:
            rolling_hash = (0,0,0)
            for ch in word:
                (h1, h2, h3) = rolling_hash
                (m1,m2,m3) = modulos
                n_c = ord(ch) - 96
                rolling_hash = ((h1 * 27 + n_c) % m1,(h2 * 27 + n_c) % m2, (h3 * 27 + n_c) % m3)
                rolling_hashes.add(rolling_hash)
        # set window of i to j in target
        # we can add and remove a character from the window and calculate rolling hash of current window 
        # efficiently
        i=0
        min_valid = [0]*len(target)
        


        # min_valid is the number of valid prefixes that can be concatenated together to form target[0...i]
        window_rolling_hash = (0,0,0)
        (m1,m2,m3) = modulos
        for j in range(len(target)):
            # update window rolling hash after adding target[i] to current window
            h1,h2,h3 = window_rolling_hash
            n_c = ord(target[j]) - 96
            window_rolling_hash = ((h1*27 + n_c)%m1, (h2*27 + n_c)%m2, (h3*27 + n_c)%m3)
            # keep updating i as as long as the window of target[i..j] is not a valid prefix
            while window_rolling_hash not in rolling_hashes and i <= j:
                # advance i to get the window in range
                n_c = ord(target[i]) - 96
                p1,p2,p3 = powers_27[j-i]
                # remove target[i] from the window and update window rolling hash
                (h1,h2,h3) = window_rolling_hash
                window_rolling_hash = (h1 - p1 * n_c + m1)%m1, (h2 - p2 * n_c + m2)%m2, (h3 - p3 * n_c + m3)%m3
                i += 1
            # if i goes beyond j there is no way to build target[0..j] with valid prefixes
            if i > j:
                return -1
            if i==0:
                min_valid[j] = 1
            else:
                min_valid[j] = 1 + min_valid[i-1]
        return min_valid[-1]
            



    



            



        
    

        
        
```
['Python3']