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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Nice Substring

Difficulty: Easy

Problem Description

A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. 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.

Key Insights

  • A substring is considered nice if all letters present in the substring appear in both uppercase and lowercase forms.
  • We can use a sliding window approach to explore all possible substrings efficiently.
  • A hash table (or dictionary) can be employed to track the counts of each character in the current window.
  • The length of the longest nice substring can be updated as we expand and contract the window.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1) (since the character set is limited to 52 uppercase and lowercase letters)

Solution

To solve the problem, we can use a sliding window approach to explore all possible substrings of the input string s. We will maintain a count of the characters in the current window using a hash table (or dictionary). For each substring, we will check if it is nice by ensuring that for every character present, both its uppercase and lowercase forms are also present. If a valid nice substring is found, we will compare its length with the longest found so far and update accordingly.

Code Solutions

def longestNiceSubstring(s: str) -> str:
    def is_nice(substr: str) -> bool:
        # Check if the substring is nice
        char_set = set(substr)
        for char in char_set:
            if char.lower() not in char_set or char.upper() not in char_set:
                return False
        return True

    longest_nice = ""
    n = len(s)

    # Check all substrings
    for i in range(n):
        for j in range(i + 1, n + 1):
            substr = s[i:j]
            if is_nice(substr) and len(substr) > len(longest_nice):
                longest_nice = substr

    return longest_nice
← Back to All Questions