Longest Nice Substring

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        if len(s) < 2:
            return ""

        arr = list(s)
        _set = set(arr)

        for i in range(len(arr)):
            c = arr[i]

            if c.upper() in _set and c.lower() in _set:
                continue

            sub1 = self.longestNiceSubstring(s[:i])
            sub2 = self.longestNiceSubstring(s[i+1:])

            if len(sub1) >= len(sub2):
                return sub1
            else:
                return sub2

        return s

This function, longestNiceSubstring, determines the longest nice substring within a given string s. A “nice” substring is one where for every character that is in the substring, the substring also contains its uppercase and lowercase versions.

Here’s a breakdown of how this function works:

  1. If the length of the input string s is less than 2, it immediately returns an empty string. This is because a nice string requires at least one pair of uppercase and lowercase letters.

  2. The function then converts the string s into a list arr and a set _set. The purpose of the set is to allow quick lookups of characters in the string.

  3. The function iterates over each character c in arr. For each character, it checks if both the uppercase and lowercase versions of the character exist in _set. If they do, it moves on to the next character.

  4. If either the uppercase or lowercase version of c is not in _set, it means s is not a nice string. The function then splits s into two substrings at the current index i and makes recursive calls to longestNiceSubstring on these substrings.

  5. The function compares the lengths of the two resulting substrings sub1 and sub2 and returns the longer one. If their lengths are equal, it returns sub1.

  6. If the function reaches the end of the string without finding a character that lacks its uppercase or lowercase version, it means s is a nice string. So it returns s.

This function employs a divide-and-conquer strategy. When it finds a character that’s not nice, it divides the problem into two smaller problems (the substrings before and after that character) and solves them recursively.