Nice Substring

Easy LC: Longest Nice Substring - LeetCode

1763. Longest Nice Substring

Easy

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.

Accepted

4,421

Submissions

7,544

The constraints are very relaxed, so an N^2 or even N^3 (1,000,000) would run in a blink of an eye. My solution is N^3: create a function "IsNice" that checks whether the string is nice or not (O(N)). Then do the 2-nested loops comparing all the substrings for an N^3 solution. Surprisingly, beats all the other solutions in time and space. Code is below, cheers, ACC.

public string LongestNiceSubstring(string s)
{
    string retVal = "";
    for (int i = 0; i < s.Length; i++)
    {
        string str = "";
        for (int j = i; j < s.Length; j++)
        {
            str += s[j].ToString();
            if (IsNice(str) && str.Length > retVal.Length) retVal = str;
        }
    }

    return retVal;
}

public bool IsNice(string s)
{
    int[] lowerCase = new int[26];
    int[] upperCase = new int[26];

    foreach (char c in s)
    {
        if (c >= 'a' && c <= 'z') lowerCase[(int)(c - 'a')] = 1;
        else upperCase[(int)(c - 'A')] = 1;
    }

    for (int i = 0; i < lowerCase.Length; i++)
        if (lowerCase[i] + upperCase[i] == 1) return false;

    return true;
}