# Longest Nice Substring   ## Intuition

From the description of this problem, we know that a Nice String is a string where for each letter it uses, both upper and lower case appears in this string.

Let's first consider the brute force solution.

1. To judge whether a string is a nice string, for each letter from a to z, we need to check whether it occurs in the string and whether both upper and lower case appears in the string. For example, for a letter a/A, we need to count the number of it in the string. The time complexity would be O(26 * n) = O(n). Because 26 is a constant number.
2. Next, we need to go through all the substrings of the given string, and judge whether it's a Nice Substring. The number of substrings for a string could be calculated by chosen a start point and then choose an end point which is greater than the start point. So the time complexity for choosing all the substrings would be O(n * n / 2) = O(n * n).
3. The overall time complexity would be O(n * n * n) = O(n ** 3).

Now, let's come to the input range of this problem. We are given that 1 <= s.length <= 100. So the maximul n would be 100. And the overall operation would be around O(n ** 3) = 10 ** 6.

Here we can use a small tip to check if it fits the problem. The maximum n for an O(n) solution is around 10 ** 6. So the maximum n for an O(n ** 3) solution is around 10 ** 2 = 100. And our brute force solution would not exceed the time.

## Solution

``````
import string
from collections import Counter

class Solution:
def longestNiceSubstring(self, s: str) -> str:
longest = ''
for start in range(len(s)):
for end in range(i, len(s)):
if self.isNice(s[start:end + 1]) and (end - start + 1) > len(longest):
longest = s[start:end + 1]
return longest

def isNice(self, s):
counter = set(s)
for c1, c2 in zip(string.ascii_lowercase, string.ascii_uppercase):
if (c1 in counter) != (c2 in counter):
return False
return True

``````