<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:
        #"abcabc" -> 2
        #"dabcabc" -> 1
        #"ababcdababcdf" greedy works (take shortest)
        #"ababcdababcdababcdababcdababcd" (greedy doesn't work, need to take longest)
        #scan from right to left, if add new letter? look at previous cases
        # check 1 vs 2
        # check 12 vs 34
        # check 123 vs 456
        # check 1234 vs 5678

        # loop i from n to 0
        # check if can delete [i:i+k+1], [i+k+1:2k+1], O(N^3) #precompute this in N^2 time with hashing
        # max deletions = 2+memoize max deletions starting at 2k+1 O(N^2) 

        # lookup_valid_index_dict = defaultdict(set)
        # for i in range(len(s)):
        #     for j in range(i+1, len(s)):
        #         substr = s[i:j+1]
        #         lookup_valid_index_dict[substr].add(i)

        # skip_val_lookup = defaultdict(list)
        # for substr, val_index_set in lookup_valid_index_dict.values():
        #     k = len(substr)-1
        #     for i in val_index_set:
        #         if i+k+1 in val_index_set:
        #             skip_val_lookup[i].append(i+k+1) #enables O(N^2) lookup, valid indices to skip to after deletion starting at i

        @lru_cache(None)
        def dp(j):
            if j==len(s):
                return 0
            
            max_deletions = 1
            # for i in skip_val_lookup[j]:
            for k in range(1, (len(s)-j)//2+1):
                if s[j:j+k]==s[j+k:j+2*k]:
                    max_deletions = max(max_deletions, 1+dp(j+k)) #skip ahead
            return max_deletions
        return dp(0)
4766