Longest Nice Substring

Difficulty: Easy | Acceptance: 64.30% | Paid: No Topics: Hash Table, String, Divide and Conquer, Bit Manipulation, Sliding Window

A string s is nice if, for every letter of the alphabet that appears in s, it appears in both uppercase and lowercase. For example, “abABB” is nice because ‘A’ and ‘a’ appear, and ‘B’ and ‘b’ appear. However, “abA” is not nice because ‘b’ appears but ‘B’ does not.

Given a string s, return the longest substring of s that is nice.

If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Divide and Conquer

Examples

Example 1:

Input: s = "YazaAay"
Output: "aAa"
Explanation: "aAa" is a nice substring because 'A' and 'a' appear. "YazaAay" is not nice because 'Y' and 'y' do not both appear (only 'y' appears). Another nice substring is "zaA", but "aAa" is longer.

Example 2:

Input: s = "Bb"
Output: "Bb"
Explanation: "Bb" is nice because both 'B' and 'b' appear. The whole string is a nice substring.

Example 3:

Input: s = "c"
Output: ""
Explanation: There are no nice substrings. A single character cannot be nice because its counterpart is missing.

Constraints

1 <= s.length <= 100
s consists of uppercase and lowercase English letters.

Approach 1: Brute Force

Intuition Since the string length is limited to 100, we can afford to check every possible substring. We iterate through all start and end indices, extract the substring, and verify if it is “nice”.

Steps

• Initialize a variable longest to store the result.
• Iterate through all possible starting indices i from 0 to n-1.
• Iterate through all possible ending indices j from i+1 to n.
• Extract the substring s[i...j].
• Check if the substring is nice by ensuring every character in it has its opposite case counterpart also present in the substring.
• If it is nice and longer than the current longest, update longest.
• Return longest.

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        def is_nice(sub):
            chars = set(sub)
            for c in chars:
                if c.swapcase() not in chars:
                    return False
            return True

        longest = ""
        n = len(s)
        for i in range(n):
            for j in range(i + 1, n + 1):
                sub = s[i:j]
                if is_nice(sub) and len(sub) > len(longest):
                    longest = sub
        return longest

Complexity

• Time: O(n³) — We iterate O(n²) substrings and checking niceness takes O(n).
• Space: O(1) — We use a fixed size array or set for character counts (max 52 chars).
• Notes: Simple to implement and sufficient given the constraint n ≤ 100.

Approach 2: Divide and Conquer

Intuition If a character c appears in the string s but its counterpart (uppercase/lowercase) does not, then c acts as a “divider”. No nice substring can include this character c. Therefore, the longest nice substring must lie entirely in the segments to the left or right of c. We can split the string by c and recursively solve for the segments.

Steps

• Base case: If the string length is less than 2, return empty string (cannot be nice).
• Convert the string to a set of characters for O(1) lookups.
• Iterate through the string. For each character c, check if its counterpart exists in the set.
• If a character c is found without its counterpart:
  • Split the string into two parts: left of c and right of c.
  • Recursively call the function on both parts.
  • Return the longer result of the two recursive calls.
• If the loop completes without finding a “bad” character, the entire string is nice. Return it.

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        if len(s) < 2:
            return ""
        
        chars = set(s)
        for i, c in enumerate(s):
            if c.swapcase() not in chars:
                left = self.longestNiceSubstring(s[:i])
                right = self.longestNiceSubstring(s[i+1:])
                return left if len(left) >= len(right) else right
        
        return s

Complexity

• Time: O(n²) — In the worst case (e.g., “abcd…”), we might split and recurse n times, and each recursion scans the string.
• Space: O(n²) — Due to string slicing and recursion stack depth in worst case.
• Notes: More efficient than brute force for larger inputs, though both are acceptable here.