<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>

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        # Helper function to check if a substring is nice
        def isNice(sub: str) -> bool:
            # Set to keep track of seen characters
            seen = set()
            # Traverse each character in the substring
            for ch in sub:
                # Add character to the set
                seen.add(ch)
            # Check if each character's uppercase and lowercase counterparts are present
            for ch in seen:
                # If 'ch' is uppercase, check if its lowercase counterpart exists and vice versa
                if (ch.islower() and ch.upper() not in seen) or (ch.isupper() and ch.lower() not in seen):
                    return False
            return True

        # Initialize variables to keep track of the longest nice substring
        max_length = 0
        longest_substr = ""
        
        # Traverse each substring of 's'
        n = len(s)
        for start in range(n):
            for end in range(start + 1, n + 1):
                # Extract the substring
                substr = s[start:end]
                # Check if the substring is nice
                if isNice(substr):
                    # Update the longest nice substring if this one is longer
                    if len(substr) > max_length:
                        max_length = len(substr)
                        longest_substr = substr
        
        return longest_substr

# Time Complexity: O(n^3) 
# Explanation: We have two nested loops to generate all substrings, which takes O(n^2) time, 
# and the isNice function which takes O(n) time for each substring, resulting in an overall time complexity of O(n^3).

# Space Complexity: O(n)
# Explanation: The space used is proportional to the size of the substring, 
# and the set used in the isNice function also has a space complexity of O(n) in the worst case.

        
139