Longest Nice Substring

Problem

A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear. However, "abA" is not because 'b' appears, but 'B' does not.

Given a string s, return the longestsubstring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.

Examples

Example 1

1
2
3
4


Input: s = "YazaAay"
Output: "aAa"
Explanation: "aAa" is a nice string because 'A/a' is the only letter of the alphabet in s, and both 'A' and 'a' appear.
"aAa" is the longest nice substring.

Example 2

1
2
3


Input: s = "Bb"
Output: "Bb"
Explanation: "Bb" is a nice string because both 'B' and 'b' appear. The whole string is a substring.

Example 3

1
2
3


Input: s = "c"
Output: ""
Explanation: There are no nice substrings.

Constraints

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

Solution

Method 1 – Divide and Conquer (1)

Intuition

A substring is nice if for every character, both its lowercase and uppercase forms are present. If a character violates this, any nice substring must be fully on one side of it. We can recursively split on such characters.

Approach

If the string length is less than 2, return an empty string.
Build a set of all characters in the string.
For each character, if both its lowercase and uppercase forms are present, continue. Otherwise, split the string at this character and recursively solve both sides.
Return the longer nice substring found, or the leftmost if equal.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
public:
    string longestNiceSubstring(string s) {
        if (s.size() < 2) return "";
        unordered_set<char> st(s.begin(), s.end());
        for (int i = 0; i < s.size(); ++i) {
            if (st.count(tolower(s[i])) && st.count(toupper(s[i]))) continue;
            string left = longestNiceSubstring(s.substr(0, i));
            string right = longestNiceSubstring(s.substr(i+1));
            return left.size() >= right.size() ? left : right;
        }
        return s;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func longestNiceSubstring(s string) string {
    if len(s) < 2 {
        return ""
    }
    st := map[byte]bool{}
    for i := 0; i < len(s); i++ {
        st[s[i]] = true
    }
    for i := 0; i < len(s); i++ {
        if st[s[i]|32] && st[s[i]&^32] {
            continue
        }
        left := longestNiceSubstring(s[:i])
        right := longestNiceSubstring(s[i+1:])
        if len(left) >= len(right) {
            return left
        }
        return right
    }
    return s
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    fun longestNiceSubstring(s: String): String {
        if (s.length < 2) return ""
        val st = s.toSet()
        for (i in s.indices) {
            if (st.contains(s[i].lowercaseChar()) && st.contains(s[i].uppercaseChar())) continue
            val left = longestNiceSubstring(s.substring(0, i))
            val right = longestNiceSubstring(s.substring(i+1))
            return if (left.length >= right.length) left else right
        }
        return s
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        if len(s) < 2:
            return ""
        st = set(s)
        for i, c in enumerate(s):
            if c.lower() in st and c.upper() in st:
                continue
            left = self.longestNiceSubstring(s[:i])
            right = self.longestNiceSubstring(s[i+1:])
            return left if len(left) >= len(right) else right
        return s

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


impl Solution {
    pub fn longest_nice_substring(s: String) -> String {
        if s.len() < 2 { return String::new(); }
        let st: std::collections::HashSet<char> = s.chars().collect();
        for (i, c) in s.chars().enumerate() {
            if st.contains(&c.to_ascii_lowercase()) && st.contains(&c.to_ascii_uppercase()) { continue; }
            let left = Solution::longest_nice_substring(s[..i].to_string());
            let right = Solution::longest_nice_substring(s[i+1..].to_string());
            return if left.len() >= right.len() { left } else { right };
        }
        s
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    longestNiceSubstring(s: string): string {
        if (s.length < 2) return "";
        const st = new Set(s);
        for (let i = 0; i < s.length; i++) {
            if (st.has(s[i].toLowerCase()) && st.has(s[i].toUpperCase())) continue;
            const left = this.longestNiceSubstring(s.slice(0, i));
            const right = this.longestNiceSubstring(s.slice(i+1));
            return left.length >= right.length ? left : right;
        }
        return s;
    }
}

Complexity

⏰ Time complexity: O(n^2 * 26), where n is the length of s. Each split may check all characters.
🧺 Space complexity: O(n^2), due to recursion and substring copies.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Divide and Conquer (1)#

Intuition#

Approach#

Code#

Complexity#