<p>A string <code>s</code> is <strong>nice</strong> if, for every letter of the alphabet that <code>s</code> contains, it appears <strong>both</strong> in uppercase and lowercase. For example, <code>&quot;abABB&quot;</code> is nice because <code>&#39;A&#39;</code> and <code>&#39;a&#39;</code> appear, and <code>&#39;B&#39;</code> and <code>&#39;b&#39;</code> appear. However, <code>&quot;abA&quot;</code> is not because <code>&#39;b&#39;</code> appears, but <code>&#39;B&#39;</code> does not.</p>

<p>Given a string <code>s</code>, return <em>the longest <strong>substring</strong> of <code>s</code> that is <strong>nice</strong>. If there are multiple, return the substring of the <strong>earliest</strong> occurrence. If there are none, return an empty string</em>.</p>

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

<pre>
<strong>Input:</strong> s = &quot;YazaAay&quot;
<strong>Output:</strong> &quot;aAa&quot;
<strong>Explanation: </strong>&quot;aAa&quot; is a nice string because &#39;A/a&#39; is the only letter of the alphabet in s, and both &#39;A&#39; and &#39;a&#39; appear.
&quot;aAa&quot; is the longest nice substring.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;Bb&quot;
<strong>Output:</strong> &quot;Bb&quot;
<strong>Explanation:</strong> &quot;Bb&quot; is a nice string because both &#39;B&#39; and &#39;b&#39; appear. The whole string is a substring.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;c&quot;
<strong>Output:</strong> &quot;&quot;
<strong>Explanation:</strong> There are no nice substrings.
</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 100</code></li>
	<li><code>s</code> consists of uppercase and lowercase English letters.</li>
</ul>

from collections import defaultdict

class Solution:
    def longestNiceSubstring(self, s: str) -> str:


        best_length: int = 0
        best_pos: int = 0


        def find_longest(max_type_count: int) -> None:            

            nonlocal best_length, best_pos

            unique_types: set[str] = set()
            unique_lower: defaultdict[str, int] = defaultdict(lambda : 0)
            unique_upper: defaultdict[str, int] = defaultdict(lambda : 0)


            substr_start_pos: int = -1
            pos: int = 0

            while pos < len(s):

                char: str = s[pos]

                if char.lower() in unique_types:
                    # такой тип уже встречался
                    if char.lower() == char:
                        unique_lower[char] += 1
                    else:
                        unique_upper[char] += 1
                else:
                    # новый тип
                    if len(unique_types) < max_type_count:
                        # еще можем добавлять новый тип
                        if len(unique_types) == 0:
                            substr_start_pos = pos
                        unique_types.add(char.lower())
                        if char.lower() == char:
                            unique_lower[char] += 1
                        else:
                            unique_upper[char] += 1
                        
                    else:
                        # нет места для новых типов
                        # конец подстроки
                        if pos - substr_start_pos > best_length:
                            is_valid_substring: bool = True
                            for curr_char in unique_types:
                                if unique_lower[curr_char.lower()] == 0 or unique_upper[curr_char.upper()] == 0:
                                    is_valid_substring = False
                                    break
                            if is_valid_substring:
                                best_pos = substr_start_pos
                                best_length = pos - substr_start_pos                            
                        
                        unique_types.add(char.lower())
                        if char.lower() == char:
                            unique_lower[char] += 1
                        else:
                            unique_upper[char] += 1
                        # перемещаем левый край окна, чтобы можно было вставить новый тип
                        while len(unique_types) > max_type_count:
                            curr_char: str = s[substr_start_pos]
                            if curr_char.lower() == curr_char:
                                unique_lower[curr_char] -= 1
                            else:
                                unique_upper[curr_char] -= 1
                            if unique_lower[curr_char.lower()] == 0 and unique_upper[curr_char.upper()] == 0:
                                unique_types.remove(curr_char.lower())
                            
                            substr_start_pos += 1

                        
                            


                
                pos += 1
            
            if pos - substr_start_pos > best_length:
                is_valid_substring: bool = True
                for curr_char in unique_types:
                    if unique_lower[curr_char.lower()] == 0 or unique_upper[curr_char.upper()] == 0:
                        is_valid_substring = False
                        break
                if is_valid_substring:
                    best_pos = substr_start_pos
                    best_length = pos - substr_start_pos






        unique_low_chars: set[str] = set(s.lower())

        for max_type_count in range(1, len(unique_low_chars) + 1):

            find_longest(max_type_count)


        return s[best_pos: best_pos + best_length]



57