Longest Nice Substring

Problem Id: 1763 Difficulty: Easy Tag: String


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