<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;= 50</code></li>
	<li><code>s</code> consists of only lowercase English letters.</li>
</ul>

class Solution:
    def maximumLength(self, s: str) -> int:
        # 2:19 - 
        # special means 1 letter+: ddd, zz, f
        # longest special str that shows up 3 times
        # or -1

        # aaaa: aa happens 3 times
        # abcdef: nothing
        # abcaba: a hapens 3 times

        # hashmap tracking how many times a substr happens {a: 4, aa: 3, aaa: 2, aaaa: 1}

        # build it as I loop: {a:1, b: 1, ab: 1, bc:1, c: 1, abc: 1, bca: 1, abca: 1, } - O(n!)

        # DP?
        # f(abcaba) = 

        # sliding window?

        # a happens 3 times
        # ab does not
        # b does not

        # ex1
        # a happens 3 times
        # aa happens 3 times
        # aaa doesn't happen 3 times

        # abcabcbbcb

        # a : no
        # b : yes
        # bc: yes
        # bca: no
        # ca: no

        # O(n^2)

        # optimization with hashmap: {a:2, b:4, c:3} you can skip anything involving a

        # sliding window algorithm:
        # if special, expand to right
        # if not, shrink from left
        #.  if can't shrink further, go to right altogether

        len_s = len(s)

        # does substring[left:right inclusive] happen two more times?
        def is_special(left: int, right: int) -> bool: 
            for i in range(left, right):
                if s[i] != s[i+1]:
                    return False
            # example: aabbccddee len=8, left=1, right=3
            sublen = right - left + 1
            occurences = 1
            for i in range(left + 1, len_s - sublen + 1):
                if s[i:i + sublen] == s[left:left + sublen]:
                    occurences += 1
            if occurences >= 3:
                return True
            else:
                return False


        left = 0
        right = 0
        max_len = -1

        # s = "aaaa":  l=0, r=0, sublen=1, occ=1, i(1, 4), True, max_len=1, 
        # l=0, r=1, sublen=2, occ=1, i(1, 3)
        while left < len_s and right < len_s: 
            if is_special(left, right):
                print('%s starting from %d is special' % (s[left:right+1], left))
                max_len = max(max_len, right - left + 1)
                right += 1
            else:
                left += 1
                if left > right:
                    right = left

        return max_len












    def maximumLengthA(self, s: str) -> int:
        # create array of (letter, consecutive occurences)

        occ_array = []

        prev_c = None
        sublen = 0
        # "aaaa", ss=a, ss=aa, 
        # {a:4}
        for c in s:
            if prev_c != c:
                # if I'm a new char, save sublen so far and reset substr
                if prev_c: 
                    occ_array.append((prev_c, sublen))
                sublen = 1
            else: 
                # if I'm same char, add to substr
                sublen += 1

            prev_c = c
        if prev_c: 
            occ_array.append((prev_c, sublen))

        #print('occ_array: ', occ_array)

        # compress occ_array
        occ_dict = defaultdict(list)
        for char, occ in occ_array:
            occ_dict[char].append(occ)
        #print('occ_dict: ', occ_dict)

        #[4]
        def max_sub(arr):
            try_max = max(arr)
            
            for i in range(try_max, 0, -1):
                total = 0
                for num in arr:
                    total += num - i + 1
                if total >= 3:
                    return i
            return -1
        # walk through occ dict
        # a: [4] means aaaa
        maxlen = -1
        for ch in occ_dict.keys():
            maxsub = max_sub(occ_dict[ch])
            maxlen = max(maxlen, maxsub)
            # what about: aaaa: 1

        return maxlen

    def maximumLengthD(self, s: str) -> int:
        # 1:12 - 
        # s
        # special meaning 1 letter

        # aaaa : aa happens three times
        # abcdef: none happens more than once
        # abcaba: a happens three times

        # {a: [0, 1, 2, 3]}
        # dictionary of contiguous letters?
        # a:[0,1,2,3], aa:[0,1,2], aaa:[0,1], aaaa[0]

        # loop over s
        
        # if I'm same char, add to substr (add both a and aa)
        # then loop over dict

        hashmap = defaultdict(int)

        prev_c = None
        substr = None
        # "aaaa", ss=a, ss=aa, 
        # {a:4, aa:3, aaa:2, a:1}
        for c in s:
            if prev_c != c:
                # if I'm a new char, reset substr
                substr = c
            else: 
                # if I'm same char, add to substr
                substr += c
            for i in range(len(substr)):
                hashmap[substr[0:i+1]] += 1
            prev_c = c
        #print('hashmap: ', hashmap)
        
        max_substr_len = -1
        for substr in hashmap.keys():
            if hashmap[substr] >= 3:
                max_substr_len = max(max_substr_len, len(substr))

        return max_substr_len
        # stor O(n)
        # comp O(n * n)
137