Longest Nice Substring

easy sliding window string set

Problem

A string is nice if for every letter it contains, that letter appears in both uppercase and lowercase. For example "abABB" is nice ('A','a' and 'B','b' both appear), but "abA" is not ('b' appears without 'B'). Given a string s, return the longest nice substring; if several tie, return the earliest one, and if none exists return the empty string.

Inputs = "YazaAay"

Output"aAa"

"aAa" uses only 'A/a', and both cases appear — it is the longest nice substring.

Inputs = "Bb"

Output"Bb"

Both 'B' and 'b' appear, so the whole string is nice.

s (letters only)

def longest_nice_substring(s):
    best = ""
    for i in range(len(s)):
        seen = set()
        for j in range(i, len(s)):
            seen.add(s[j])
            nice = all((c.lower() in seen) and (c.upper() in seen)
                       for c in seen)
            if nice and j - i + 1 > len(best):
                best = s[i:j + 1]
    return best

function longestNiceSubstring(s) {
  let best = "";
  for (let i = 0; i < s.length; i++) {
    const seen = new Set();
    for (let j = i; j < s.length; j++) {
      seen.add(s[j]);
      let nice = true;
      for (const c of seen)
        if (!seen.has(c.toLowerCase()) || !seen.has(c.toUpperCase()))
          nice = false;
      if (nice && j - i + 1 > best.length)
        best = s.slice(i, j + 1);
    }
  }
  return best;
}

String longestNiceSubstring(String s) {
    String best = "";
    for (int i = 0; i < s.length(); i++) {
        Set<Character> seen = new HashSet<>();
        for (int j = i; j < s.length(); j++) {
            seen.add(s.charAt(j));
            boolean nice = true;
            for (char c : seen)
                if (!seen.contains(Character.toLowerCase(c)) ||
                    !seen.contains(Character.toUpperCase(c)))
                    nice = false;
            if (nice && j - i + 1 > best.length())
                best = s.substring(i, j + 1);
        }
    }
    return best;
}

string longestNiceSubstring(string s) {
    string best = "";
    for (int i = 0; i < s.size(); i++) {
        set<char> seen;
        for (int j = i; j < s.size(); j++) {
            seen.insert(s[j]);
            bool nice = true;
            for (char c : seen)
                if (!seen.count(tolower(c)) || !seen.count(toupper(c)))
                    nice = false;
            if (nice && j - i + 1 > (int)best.size())
                best = s.substr(i, j - i + 1);
        }
    }
    return best;
}

Explanation

Because the string is short (length ≤ 100), we can afford to examine every substring directly. We fix a start index i and let a window grow to the right with end index j, so each step considers the substring s[i..j].

As the window expands we maintain a set seen of the characters currently inside it. Adding the new character s[j] is O(1), so growing the window is cheap.

A window is nice when, for every character it contains, both the lowercase and uppercase form are also present in the set. We check this by scanning seen: if any character is missing its opposite case, the window is not nice.

Whenever the current window is nice and strictly longer than the best found so far, we record it as the new answer. Because we scan start indices left to right and only replace on a strictly longer window, the earliest of any tied longest substrings is naturally kept.

For s = "YazaAay" the window "aAa" (indices 3–5) is nice and is the longest such window, so it is the answer.

Time: O(n²·26) Space: O(26)