<p>You are given a string <code>s</code> consisting of only lowercase English letters. In one operation, you can:</p>

<ul>
	<li>Delete <strong>the entire string</strong> <code>s</code>, or</li>
	<li>Delete the <strong>first</strong> <code>i</code> letters of <code>s</code> if the first <code>i</code> letters of <code>s</code> are <strong>equal</strong> to the following <code>i</code> letters in <code>s</code>, for any <code>i</code> in the range <code>1 &lt;= i &lt;= s.length / 2</code>.</li>
</ul>

<p>For example, if <code>s = &quot;ababc&quot;</code>, then in one operation, you could delete the first two letters of <code>s</code> to get <code>&quot;abc&quot;</code>, since the first two letters of <code>s</code> and the following two letters of <code>s</code> are both equal to <code>&quot;ab&quot;</code>.</p>

<p>Return <em>the <strong>maximum</strong> number of operations needed to delete all of </em><code>s</code>.</p>

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

<pre>
<strong>Input:</strong> s = &quot;abcabcdabc&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong>
- Delete the first 3 letters (&quot;abc&quot;) since the next 3 letters are equal. Now, s = &quot;abcdabc&quot;.
- Delete all the letters.
We used 2 operations so return 2. It can be proven that 2 is the maximum number of operations needed.
Note that in the second operation we cannot delete &quot;abc&quot; again because the next occurrence of &quot;abc&quot; does not happen in the next 3 letters.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;aaabaab&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong>
- Delete the first letter (&quot;a&quot;) since the next letter is equal. Now, s = &quot;aabaab&quot;.
- Delete the first 3 letters (&quot;aab&quot;) since the next 3 letters are equal. Now, s = &quot;aab&quot;.
- Delete the first letter (&quot;a&quot;) since the next letter is equal. Now, s = &quot;ab&quot;.
- Delete all the letters.
We used 4 operations so return 4. It can be proven that 4 is the maximum number of operations needed.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;aaaaa&quot;
<strong>Output:</strong> 5
<strong>Explanation:</strong> In each operation, we can delete the first letter of s.
</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 4000</code></li>
	<li><code>s</code> consists only of lowercase English letters.</li>
</ul>

class Solution:
    def deleteString(self, s: str) -> int:
        # Rolling HASH + Dynamic programing: O(n^2), O(n)
        cache = {len(s): 0}
        BASE = 31
        MOD = 10**9 + 7
        prefix_hashes = [0] * len(s)
        prefix_pow = [1] * len(s)
        def get_num(char):
            return ord(char)

        for i in range(len(s)):
            if i == 0:
                prefix_hashes[i] = get_num(s[i])
            else:
                prefix_hashes[i] = (prefix_hashes[i-1] * BASE + get_num(s[i])) % MOD
                prefix_pow[i] = (prefix_pow[i-1] * BASE) % MOD

        def is_valid(i, j):
            # print(i, j)
            head_start = i
            head_end = j - 1
            tail_start = j
            tail_end = 2*j - i - 1
            head_hash, tail_hash = 0, 0
            if tail_end >= len(s):
                return False
            if head_start == 0:
                head_hash = prefix_hashes[head_end]
            else:
                head_hash = (prefix_hashes[head_end] - prefix_hashes[head_start-1] * prefix_pow[head_end - head_start + 1] % MOD + MOD) % MOD 
            tail_hash = (prefix_hashes[tail_end] - prefix_hashes[tail_start-1] * prefix_pow[tail_end - tail_start + 1] % MOD + MOD) % MOD
            return head_hash == tail_hash
             
        def dfs(i):
            if i in cache: return cache[i]
            local_res = 1
            for j in range(i+1, (len(s) + i)//2 + 1 ):
                # check i->j-1 valid
                if is_valid(i,j):
                    local_res = max(local_res, 1 + dfs(j))
            cache[i] = local_res
            return cache[i]
        
        dfs(0)
        return cache[0]
7788