We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Nice Substring

Number: 1873

Difficulty: Easy

Paid? No

Companies: Google, Microsoft

Problem Description

Given a string s, a substring is called nice if every letter in the substring appears in both uppercase and lowercase. The task is to return the longest nice substring. If there are multiple answers, return the one that occurs earliest in s. If no such substring exists, return an empty string.

Key Insights

  • A substring is considered nice if for every character, both its uppercase and lowercase forms are present.
  • To check if a substring is nice, using a set to quickly verify the presence of both cases is effective.
  • Due to the small constraint (s.length <= 100), an O(n^3) brute-force solution is acceptable, but an efficient divide-and-conquer method can also be applied.
  • The divide-and-conquer technique works by identifying an offending character (one missing its counterpart) and then recursively solving for the segments on both sides.
  • Keeping track of the earliest occurrence for substrings of the same length is necessary when multiple valid candidates exist.

Space and Time Complexity

Time Complexity: O(n^2) to O(n^3) in the worst-case scenario if using brute force; however, the divide and conquer approach typically performs faster in practice. Space Complexity: O(n) due to recursion and auxiliary data structures (sets).

Solution

We can solve the problem using a recursive divide-and-conquer approach:

  1. Check if the current string is nice. We do this by creating a set of characters in the string and confirming for each character that its opposite case also exists.
  2. If the string is nice, return it as a candidate.
  3. If not, find the first offending character that violates the niceness condition.
  4. Recursively call the function for the two substrings split at the offending character, and return the longer of the two valid nice substrings.
  5. This approach ensures that we consider every possibility while naturally skipping segments that cannot form a nice substring.

Code Solutions

# Python solution for Longest Nice Substring
def longestNiceSubstring(s: str) -> str:
    # Helper function to check if a substring is nice
    def is_nice(sub: str) -> bool:
        # Create a set of characters in the substring
        char_set = set(sub)
        # For each character, check if its opposite case exists
        for ch in char_set:
            if ch.swapcase() not in char_set:
                return False
        return True

    # Recursive function using divide and conquer approach
    def helper(sub: str) -> str:
        # Base case: if the substring is too short, it cannot be nice
        if len(sub) < 2:
            return ""
        # For each character, if it's offending (not forming a nice pair), split and solve recursively
        for i, ch in enumerate(sub):
            if ch.swapcase() not in sub:
                # Recurse on the left part and right part
                left = helper(sub[:i])
                right = helper(sub[i+1:])
                # Return the longer substring; if same length, left portion appears earlier
                return left if len(left) >= len(right) else right
        # If the loop finishes, the substring is nice
        return sub

    return helper(s)

# Example usage:
print(longestNiceSubstring("YazaAay"))  # Expected output: "aAa"
← Back to All Questions