1763. Longest Nice Substring

This problem asks to find the longest substring within a given string s that is "nice". A nice string is defined as a string where for every letter present, both its uppercase and lowercase versions are also present.

Approach

The solutions employ a sliding window approach combined with bit manipulation or set operations to efficiently check for "niceness". The core idea revolves around iterating through all possible substrings and checking if each substring satisfies the nice string criteria.

Solution 1: Using Sets

This solution uses a HashSet (or set in Python) to store the characters encountered in each substring. For every substring:

1. Iterate through Substrings: The outer loop iterates through all possible starting positions (i) of substrings. The inner loop extends the substring from i to j.

2. Populate Set: As the inner loop iterates, it adds each character to the HashSet.

3. Check for Niceness: After adding a character, the code checks if the set contains both the uppercase and lowercase versions of each character in the set. If not, the substring is not nice.

4. Update Result: If a nice substring is found, and its length is greater than the current longest nice substring, the result is updated.

Time Complexity: O(n^3), where n is the length of the string. This is because the nested loops can iterate up to n*n times, and the inner check for niceness can take O(n) in the worst case (checking for each character in the set). However, the set operations usually have better than O(n) average time.

Space Complexity: O(n) in the worst case, to store the set of characters in a substring.

Solution 2: Using Bit Manipulation

This solution optimizes the niceness check using bit manipulation. It uses two integers, lower and upper, to represent the lowercase and uppercase letters present in the current substring. Each bit in these integers corresponds to a letter of the alphabet (a=0, b=1, etc.). A bit is set to 1 if the corresponding letter is present.

1. Iterate through Substrings: Similar to Solution 1, this solution iterates through all possible substrings.

2. Update Bitmasks: For each character, the corresponding bit in either lower or upper is set based on whether the character is lowercase or uppercase.

3. Check for Niceness: A substring is nice if and only if lower is equal to upper. This is because both bitmasks will be identical if all letters have both their uppercase and lowercase counterparts present.

4. Update Result: If a nice substring is found, and it's longer than the current longest, the result is updated.

Time Complexity: O(n^2). The nested loops dominate the time complexity. The bitwise operations are constant time.

Space Complexity: O(1). Only constant extra space is used for the lower, upper integers and the result string.

Code Examples (Python)

Solution 1 (Sets):

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        n = len(s)
        ans = ''
        for i in range(n):
            ss = set()
            for j in range(i, n):
                ss.add(s[j])
                if all(c.lower() in ss and c.upper() in ss for c in ss) and len(ans) < j - i + 1:
                    ans = s[i:j + 1]
        return ans
 

Solution 2 (Bit Manipulation):

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        n = len(s)
        ans = ""
        for i in range(n):
            lower = upper = 0
            for j in range(i, n):
                if s[j].islower():
                    lower |= 1 << (ord(s[j]) - ord('a'))
                else:
                    upper |= 1 << (ord(s[j]) - ord('A'))
                if lower == upper and len(ans) < j - i + 1:
                    ans = s[i:j + 1]
        return ans

The bit manipulation approach (Solution 2) provides a more efficient solution due to its O(n^2) time complexity compared to Solution 1's O(n^3) (though average case of Solution 1 is likely better than the worst case). Both solutions have a space complexity that is at most linear in the input size. Choose the solution which best suits your needs considering readability and performance. For most cases, the slight performance gain from bit manipulation might not be significant unless dealing with very large input strings.