<p>You are given a string <code>s</code> that consists of lowercase English letters.</p>

<p>A string is called <strong>special</strong> if it is made up of only a single character. For example, the string <code>&quot;abc&quot;</code> is not special, whereas the strings <code>&quot;ddd&quot;</code>, <code>&quot;zz&quot;</code>, and <code>&quot;f&quot;</code> are special.</p>

<p>Return <em>the length of the <strong>longest special substring</strong> of </em><code>s</code> <em>which occurs <strong>at least thrice</strong></em>, <em>or </em><code>-1</code><em> if no special substring occurs at least thrice</em>.</p>

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

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

<pre>
<strong>Input:</strong> s = &quot;aaaa&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> The longest special substring which occurs thrice is &quot;aa&quot;: substrings &quot;<u><strong>aa</strong></u>aa&quot;, &quot;a<u><strong>aa</strong></u>a&quot;, and &quot;aa<u><strong>aa</strong></u>&quot;.
It can be shown that the maximum length achievable is 2.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;abcdef&quot;
<strong>Output:</strong> -1
<strong>Explanation:</strong> There exists no special substring which occurs at least thrice. Hence return -1.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;abcaba&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> The longest special substring which occurs thrice is &quot;a&quot;: substrings &quot;<u><strong>a</strong></u>bcaba&quot;, &quot;abc<u><strong>a</strong></u>ba&quot;, and &quot;abcab<u><strong>a</strong></u>&quot;.
It can be shown that the maximum length achievable is 1.
</pre>

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

<ul>
	<li><code>3 &lt;= s.length &lt;= 5 * 10<sup>5</sup></code></li>
	<li><code>s</code> consists of only lowercase English letters.</li>
</ul>

class Solution:
    def maximumLength(self, s: str) -> int:
        # returns map from char to longest special substring of that char
        # if the longest substring is n, and n >= 3, then we know we have >=3 instances of (n-2) length substrings of that char
        # we should store the values in a heap, and starting from the max value, we check if it occurs >= 3 times in s
        # if it does, we make that the longest length
        # if it only occurs twice, we can make (n-1) the longest length
        # if it only occurs once, we need to check how many times (n-1) occurs. If >= 3, then (n-1) is longest. If <3, then (n-2) is longest
        # if the next value we get from the heap is smaller than the longest, then we are done
        specialSubstringsMap = self.collectSpecialSubstrings(s)
        
        specialSubstringsHeap = [(-specialSubstringsMap[key][0], key) for key in specialSubstringsMap]
        heapq.heapify(specialSubstringsHeap)
        print(specialSubstringsMap)
                
        longestSpecial = 0
        while len(specialSubstringsHeap) > 0:
            currLength, currChar = heapq.heappop(specialSubstringsHeap)
            currLength = -currLength
            if currLength < longestSpecial:
                break
            if specialSubstringsMap[currChar][1] >= 3:
                longestSpecial = currLength
            elif specialSubstringsMap[currChar][2] >= 3:
                longestSpecial = max(longestSpecial, currLength-1)
            else:
                if currLength >= 3:
                    longestSpecial = max(longestSpecial, currLength-2)
            
        if longestSpecial == 0:
            return -1
        
        return longestSpecial
        
        
    def collectSpecialSubstrings(self, s):
        specialSubstrings = dict()
        start = 0
        end = 0
        currIter = False
        while start < len(s):
            while end < len(s) and s[end] == s[start]:
                if s[start] not in specialSubstrings:
                    specialSubstrings[s[start]] = [1, 1, 0]
                    currIter = True
                else:
                    # longer special substring, we want to start keeping track of how many there are of those
                    # but we still want to keep track of (n-1) substring too
                    # we keep track of [longest length, # of longest length, # of length-1]
                    if len(s[start:end+1]) > specialSubstrings[s[start]][0]:
                        currInstances = specialSubstrings[s[start]][1]
                        # if we just updated specialSubstrings[s[start]] on this current iteration
                        if currIter:
                            currInstances += 1
                        # if we updated specialSubstrings[s[start]] on a past iteration
                        else:
                            currInstances += 2
                        specialSubstrings[s[start]] = [len(s[start:end+1]), 1, currInstances]
                        currIter = True
                    elif len(s[start:end+1]) == specialSubstrings[s[start]][0]:
                        specialSubstrings[s[start]][1] += 1
                        specialSubstrings[s[start]][2] += 2
                    elif len(s[start:end+1])+1 == specialSubstrings[s[start]][0]:
                        specialSubstrings[s[start]][2] += 1
                # print(f"substring: {s[start:end+1]}, specialSubstrings: {specialSubstrings}")
                end += 1
            currIter = False
            start = end
            
        return specialSubstrings
                
3611