Search

Longest Nice Substring

Updated: Mar 25, 2021

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 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.


Example 1:

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:

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:

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

Example 4:

Input: s = "dDzeE"
Output: "dD"
Explanation: Both "dD" and "eE" are the longest nice substrings.
As there are multiple longest nice substrings, return "dD" since it occurs earlier.

Constraints:

  • 1 <= s.length <= 100

  • s consists of uppercase and lowercase English letters.

Solution:


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

139 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.