Domain 1EasyCORE

Longest Nice Substring

The problem asks us to find the longest substring in a given string `s` that contains every letter it includes in both uppercase and lowercase forms. A "nice" substring must have all its characters' corresponding cases present.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

1763. Longest Nice Substring

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 0
Acceptance rate: 61.5%


Problem Breakdown

The problem asks us to find the longest substring in a given string s that contains every letter it includes in both uppercase and lowercase forms. A “nice” substring must have all its characters’ corresponding cases present.

Inputs:

  • A single string s consisting of uppercase and lowercase English letters.

Outputs:

  • The longest nice substring. If multiple substrings are equally long, return the one that appears first in the original string.
  • If no such substring exists, return an empty string.

Implicit Constraints/Edge Cases:

  • The input string can be as short as 1 character or as long as 100 characters.
  • The string may contain only uppercase and lowercase letters.
  • An empty string is a valid input, but since it cannot contain any nice substrings, the output should be an empty string.

Intuition

A brute-force approach would involve checking every possible substring of s to see if it’s nice. This would have a time complexity of O(n^3) due to generating all substrings and then checking each one for niceness. This is inefficient given the constraints.

The key insight is to use a divide-and-conquer strategy. If a character in the string does not have its corresponding case, we can split the string at that character and recursively find nice substrings in the resulting parts. This approach reduces unnecessary checks and focuses only on potentially valid substrings.

Approach

  1. Base Case: If the length of s is less than 2, return an empty string because a single character cannot be nice.
  2. Character Frequency Check: Use a set to track the presence of each character in s.
  3. Identify Split Points: Iterate through the string and find characters that do not have their corresponding case present in the set. These characters are potential split points.
  4. Recursive Division: If no such character is found, the entire string is nice. Otherwise, split the string at each identified character and recursively find the longest nice substring in each part.
  5. Combine Results: Return the longest nice substring found among the recursive calls.

Complexity Analysis

  • Time Complexity: O(n^2) in the worst case due to potential multiple splits and recursive checks. However, this is significantly better than the brute-force approach.
  • Space Complexity: O(n) due to the recursion stack and the set used for character frequency tracking.

Solution

def longestNiceSubstring(s: str) -> str:
    if len(s) < 2:
        return ""
    
    # Track the presence of each character in the string
    char_set = set(s)
    
    # Find a character that does not have its corresponding case
    for i, c in enumerate(s):
        if c.lower() not in char_set or c.upper() not in char_set:
            # Split the string and recursively find nice substrings
            left = longestNiceSubstring(s[:i])
            right = longestNiceSubstring(s[i+1:])
            return max(left, right, key=len)
    
    # If no such character is found, the entire string is nice
    return s

# Example usage:
# print(longestNiceSubstring("YazaAay"))  # Output: "aAa"
# print(longestNiceSubstring("Bb"))       # Output: "Bb"
# print(longestNiceSubstring("c"))        # Output: ""
# print(longestNiceSubstring("dDzeE"))    # Output: "dD"

Edge Cases Handled

  • Empty String: Returns an empty string as expected.
  • Single Character: Returns an empty string since a single character cannot be nice.
  • All Characters Nice: The entire string is returned if all characters have their corresponding cases present.
  • Multiple Longest Substrings: The first occurring longest nice substring is returned.