Code Implementation

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

        max_sub = ""
        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(max_sub):
                    max_sub = sub
        return max_sub
      

class Solution {
public:
    string longestNiceSubstring(string s) {
        int maxLen = 0, start = 0;
        int n = s.size();
        auto isNice = [](const string& sub) {
            unordered_set<char> chars(sub.begin(), sub.end());
            for (char c : chars) {
                if (chars.count(islower(c) ? toupper(c) : tolower(c)) == 0)
                    return false;
            }
            return true;
        };
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                string sub = s.substr(i, j - i);
                if (isNice(sub) && (j - i) > maxLen) {
                    maxLen = j - i;
                    start = i;
                }
            }
        }
        return s.substr(start, maxLen);
    }
};
      

class Solution {
    public String longestNiceSubstring(String s) {
        int maxLen = 0, start = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                String sub = s.substring(i, j);
                if (isNice(sub) && (j - i) > maxLen) {
                    maxLen = j - i;
                    start = i;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }

    private boolean isNice(String sub) {
        Set<Character> chars = new HashSet<>();
        for (char c : sub.toCharArray()) {
            chars.add(c);
        }
        for (char c : chars) {
            if (!chars.contains(Character.isLowerCase(c) ? Character.toUpperCase(c) : Character.toLowerCase(c))) {
                return false;
            }
        }
        return true;
    }
}
      

var longestNiceSubstring = function(s) {
    function isNice(sub) {
        let chars = new Set(sub);
        for (let c of chars) {
            if (!chars.has(
                c === c.toLowerCase() ? c.toUpperCase() : c.toLowerCase()
            )) {
                return false;
            }
        }
        return true;
    }
    let maxSub = "";
    for (let i = 0; i < s.length; ++i) {
        for (let j = i + 1; j <= s.length; ++j) {
            let sub = s.slice(i, j);
            if (isNice(sub) && sub.length > maxSub.length) {
                maxSub = sub;
            }
        }
    }
    return maxSub;
};
      

Problem Description

Given a string s, find the longest substring of s such that for every character in the substring, both its uppercase and lowercase forms also appear in the substring. Such a substring is called "nice". If there are multiple longest nice substrings, return the one that appears first. If there is no nice substring, return an empty string.

• All characters in s are English letters.
• The answer must be a contiguous substring of s.
• If several answers exist, return the one with the lowest starting index.

Thought Process

The problem asks for the longest substring where every character's uppercase and lowercase forms are both present. At first, it's tempting to check every possible substring, but that would be inefficient for large strings.

The brute-force approach is to consider all substrings and check if each is "nice". However, this is slow because the number of substrings grows quadratically with the length of s.

To optimize, we need a way to quickly check if a substring is "nice", and possibly avoid checking substrings that cannot possibly be nice (for example, if a character only appears in one case). However, since the constraints are modest (string length up to 100), the brute-force approach is acceptable and simple to implement.

Solution Approach

• Step 1: Iterate through all possible substrings of s. For each starting index i, and ending index j, consider the substring s[i:j].
• Step 2: For each substring, check if it is "nice". To do this:
  • Create a set of all characters in the substring.
  • For each character, check if its counterpart (uppercase if it's lowercase, and vice versa) is also in the set.
• Step 3: If the substring is "nice" and longer than the previously found "nice" substring, update the result.
• Step 4: After checking all substrings, return the longest one found.

We use sets for quick character existence checking, which is O(1) per check. The double loop ensures all substrings are considered, and the check for "niceness" is linear in the length of the substring.

Example Walkthrough

Consider s = "YazaAay".

• Start with substring "Y": only 'Y' exists, so not nice.
• Try "Ya": contains 'Y' and 'a', but 'y' is missing, so not nice.
• Try "Yaz": contains 'Y', 'a', 'z', but 'y', 'A', 'Z' are missing.
• Continue until "aAa": contains 'a', 'A', but 'y' is missing.
• Try "aAa", "aAa", "aAay" etc. Eventually, "aAa" is found to be nice because both 'a' and 'A' are present, and the substring is as long as possible under the rules.
• Therefore, the answer is "aAa".

The algorithm checks all substrings and updates the result whenever a longer nice substring is found.

Time and Space Complexity

• Brute-force approach:
  • There are O(N²) substrings in a string of length N.
  • For each substring, checking if it is nice takes O(N) time (since the substring can be up to length N).
  • Total time complexity: O(N³).
  • Space complexity: O(N) for the set used to check each substring.
• Optimized approaches:
  • With more advanced techniques (divide and conquer, bitmasking), time can be reduced, but for small N, brute-force is sufficient.

Summary

The key insight is that a "nice" substring must contain both cases for every letter present. By checking all possible substrings and verifying this property using a set for fast lookups, we can find the longest nice substring efficiently for small input strings. The brute-force approach is clear and effective given the constraints, and the solution is easy to implement in multiple languages.