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