Problem statement

A string is nice if, for every letter it contains, it contains both the uppercase and the lowercase form. "abABB" is nice; "abA" is not, because b appears without B.

Return the longest nice substring of s. If there are several of the same maximum length, return the one that starts earliest. If none exists, return the empty string.

Example 1

Input: s = "YazaAay"
Output: aAa
Explanation: "aAa" is nice; the surrounding letters break the pairing.

Example 2

Input: s = "Bb"
Output: Bb

Example 3

Input: s = "c"
Output: 
Explanation: A single letter can never be nice.

Constraints

• 1 <= s.length <= 100
• s consists of uppercase and lowercase English letters.

Hints for Longest Nice Substring

1. Hint 1

   If some character's counterpart is missing from the whole string, no nice substring can cross that character.

2. Hint 2

   That splits the problem: recurse on the part left of it and the part right of it.

3. Hint 3

   Prefer the left answer on a tie so the earliest start wins.

How to solve Longest Nice Substring

Divide and conquer on the first offending character — one whose opposite case is absent from the current segment. No nice substring can contain it, so the answer lies entirely to its left or entirely to its right.

Approach

1. If the segment is shorter than 2, return the empty string.
2. Collect the set of characters present.
3. Scan for the first character whose opposite case is missing from that set.
4. If found at index i, recurse on s[0..i-1] and s[i+1..] and return the longer result, preferring the left one on a tie.
5. If no offender exists, the whole segment is nice — return it.

Why it works

A nice substring containing an offending character would need that character's counterpart, which is absent from the entire segment and therefore from any substring of it. So the offender is a hard split point.

Complexity

• Time — O(n²) in the worst case
• Space — O(n) for the recursion

Pitfalls

• Returning the right answer on a tie violates the earliest-start rule — > rather than >= is what keeps the left one.
• Checking niceness for all O(n²) substrings independently is O(n³) and times out on longer inputs.
• The present-character set must be rebuilt for each segment, not reused from the parent.

Reference solution

Python

def longestNiceSubstring(s: str) -> str:
    if len(s) < 2:
        return ""
    chars = set(s)
    for i, c in enumerate(s):
        if c.swapcase() in chars:
            continue
        left = longestNiceSubstring(s[:i])
        right = longestNiceSubstring(s[i + 1:])
        return right if len(right) > len(left) else left
    return s

Java

public static String longestNiceSubstring(String s) {
    if (s.length() < 2) return "";
    HashSet<Character> set = new HashSet<>();
    for (int i = 0; i < s.length(); i++) set.add(s.charAt(i));
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        char other = Character.isLowerCase(c) ? Character.toUpperCase(c) : Character.toLowerCase(c);
        if (set.contains(other)) continue;
        String left = longestNiceSubstring(s.substring(0, i));
        String right = longestNiceSubstring(s.substring(i + 1));
        return right.length() > left.length() ? right : left;
    }
    return s;
}

C++

string longestNiceSubstring(string s) {
    if (s.size() < 2) return "";
    unordered_set<char> set;
    for (char c : s) set.insert(c);
    for (int i = 0; i < (int) s.size(); i++) {
        char c = s[i];
        char other = (c >= 'a' && c <= 'z') ? (char) (c - 32) : (char) (c + 32);
        if (set.count(other)) continue;
        string left = longestNiceSubstring(s.substr(0, i));
        string right = longestNiceSubstring(s.substr(i + 1));
        return right.size() > left.size() ? right : left;
    }
    return s;
}

JavaScript

var longestNiceSubstring = function(s) {
    if (s.length < 2) return "";
    const set = {};
    for (let i = 0; i < s.length; i++) set[s.charAt(i)] = true;
    for (let i = 0; i < s.length; i++) {
        const c = s.charAt(i);
        const other = c >= "a" && c <= "z" ? c.toUpperCase() : c.toLowerCase();
        if (set[other] === true) continue;
        const left = longestNiceSubstring(s.slice(0, i));
        const right = longestNiceSubstring(s.slice(i + 1));
        return right.length > left.length ? right : left;
    }
    return s;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Binary Tree Paths Easy
• Find Most Frequent Vowel and Consonant Easy
• Maximum Difference Between Even and Odd Frequency I Easy
• Find Valid Pair of Adjacent Digits in String Easy
• Count the Number of Special Characters I Easy
• Find Maximum Number of String Pairs Easy