<p>You are given a string <code>s</code> and a <strong>positive</strong> integer <code>k</code>.</p>

<p>Select a set of <strong>non-overlapping</strong> substrings from the string <code>s</code> that satisfy the following conditions:</p>

<ul>
	<li>The <strong>length</strong> of each substring is <strong>at least</strong> <code>k</code>.</li>
	<li>Each substring is a <strong>palindrome</strong>.</li>
</ul>

<p>Return <em>the <strong>maximum</strong> number of substrings in an optimal selection</em>.</p>

<p>A <strong>substring</strong> is a contiguous sequence of characters within a string.</p>

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

<pre>
<strong>Input:</strong> s = &quot;abaccdbbd&quot;, k = 3
<strong>Output:</strong> 2
<strong>Explanation:</strong> We can select the substrings underlined in s = &quot;<u><strong>aba</strong></u>cc<u><strong>dbbd</strong></u>&quot;. Both &quot;aba&quot; and &quot;dbbd&quot; are palindromes and have a length of at least k = 3.
It can be shown that we cannot find a selection with more than two valid substrings.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;adbcda&quot;, k = 2
<strong>Output:</strong> 0
<strong>Explanation:</strong> There is no palindrome substring of length at least 2 in the string.
</pre>

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

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

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        N = len(s)
        intervals = []
        
        # by default order intervals in increasing order
        
        # process expansion in order:
        # (0,0), (0,1), (1,1), (1,2)
        
        for left in range(N):
            for z in range(2):
                l = left
                r = l+z
                # print("-- ", l,r)
                while l >= 0 and r < N and s[l] == s[r]:
                    if r + 1 - l >= k: 
                        intervals.append((l, r))
                        break
                    l -= 1
                    r += 1
                
        n = len(intervals)
        
        # print(intervals)
        
        if n == 0:
            return 0
        
        count = 1
        prev = intervals[0][1]
       
        for i in range(1, n):
            if intervals[i][0] > prev:
                count += 1
                prev = intervals[i][1]
       
        return count
        
        
# Need to sort     
# class Solution:
#     def maxPalindromes(self, s: str, k: int) -> int:
#         intervals = []
#         n = len(s)
        
#         for i in range(len(s)):
#             # Even length palindromes
#             l = 1
#             while i+l < n and i-l+1>=0 and s[i-l+1]==s[i+l]:
#                 if (i+l - (i-l+1) + 1) >= k:
#                     intervals.append([i-l+1, i+l])
#                 l += 1
            
#             # Odd length palindromes
#             l = 0
#             while i+l < n and i-l >= 0 and s[i+l]==s[i-l]:
#                 if (i+l - (i-l) + 1) >= k:
#                     intervals.append([i-l, i+l])
#                 l += 1
        
#         intervals.sort(key=lambda x: (x[1], x[0]))
        
#         n = len(intervals)
        
#         # print(intervals)
        
#         if n == 0:
#             return 0
        
#         count = 1
#         prev = intervals[0][1]
       
#         for i in range(1, n):
#             if intervals[i][0] > prev:
#                 count += 1
#                 prev = intervals[i][1]
       
#         return count
17000