Longest Nice Substring

🏠 ⬅️ ➡️

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.

Constraints:

  • 1 <= s.length <= 100
  • s consists of uppercase and lowercase English letters.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=:), allocatable :: s
    integer :: i, j

    ! Examples
    s = "YazaAay "
    print *, longestNiceSubstring(s)
    s = "Bb "
    print *, longestNiceSubstring(s)
    s = "c "
    print *, longestNiceSubstring(s)

contains

    function longestNiceSubstring(s) result(res)
        implicit none
        character(len=*), intent(in) :: s
        character(len=:), allocatable :: res
        logical :: found

        allocate(character(len=size(s)) :: res)
        res = ""
        do i = 1, size(s) - 1
            found = .false.
            do j = 1, size(s) - i
                if (isNiceString(s(i+j:i+j))) then
                    found = .true.
                    exit
                end if
            end do
            if (found) then
                res = s(i:i+j-1)
            end if
        end do
    end function longestNiceSubstring

    function isNiceString(s) result(res)
        implicit none
        character(len=*), intent(in) :: s
        logical :: res

        res = .false.
        do i = 1, len_trim(s)
            if (index(s, char(ichar('A') + i - 1)) /= 0 .and. &
                index(s, char(ichar('a') + i - 1)) /= 0) then
                res = .true.
                exit
            end if
        end do
    end function isNiceString

end program main
❌ Compiled
❌ Executed
❌ Correct 
program longestNiceSubstring
    implicit none

    character(len=100) :: s
    integer :: i, j, n
    logical :: isNice
    character(len=100) :: niceSubstring

contains

    function isNice(s) result(isNice)
        implicit none
        character(len=*), intent(in) :: s
        integer :: i
        logical :: isNice

        isNice = .true.

        do i = 1, 26
            if (count(s == char(i + 96)) == 0 .and. count(s == char(i + 64)) == 0) then
                isNice = .false.
                exit
            end if
        end do
    end function isNice

end program longestNiceSubstring
🌐 Data from online sources 
def longestNiceSubstring(s: str) -> str:
    n = len(s)
    result = ""
    for i in range(n):
        for j in range(i + 1, n):
            is_nice = True
            for ch in range(ord('A'), ord('Z') + 1):
                upper = chr(ch) in s[i:j+1]
                lower = chr(ch + 32) in s[i:j+1]
                if (upper and not lower) or (not upper and lower):
                    is_nice = False
                    break
            if is_nice and j - i + 1 > len(result):
                result = s[i:j+1]
    return result

The algorithm iterates through all possible substrings using two nested for loops. Then, for each substring, it checks if the substring is nice. If a substring is nice and its length is greater than the current longest nice substring found, it updates the result to store the new longest nice substring.

Specifically, in the innermost loop, the algorithm checks if there is any character (in uppercase form) present and missing its counterpart (lowercase form) or vice versa. If it finds such a pair, it marks the substring as not nice and breaks the loop. If the substring is nice, it updates the result if the substring is longer than the current longest nice substring found.

🌐 Data from online sources 
#include <string>
using namespace std;

string longestNiceSubstring(string s) {
    int n = s.length();
    string result = "";
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; ++j) {
            bool isNice = true;
            for (char ch = 'A'; ch <= 'Z'; ++ch) {
                bool upper = false, lower = false;
                for (int k = i; k <= j; ++k) {
                    if (s[k] == ch) upper = true;
                    if (s[k] == (ch + 32)) lower = true;
                }
                if ((upper && !lower) || (!upper && lower)) {
                    isNice = false;
                    break;
                }
            }
            if (isNice && j - i + 1 > result.length()) {
                result = s.substr(i, j - i + 1);
            }
        }
    }
    return result;
}

The algorithm iterates through all possible substrings using two nested for loops. Then, for each substring, it checks if the substring is nice. If a substring is nice and its length is greater than the current longest nice substring found, it updates the result to store the new longest nice substring.

Specifically, in the innermost loop, the algorithm checks if there is any character (in uppercase form) present and missing its counterpart (lowercase form) or vice versa. If it finds such a pair, it marks the substring as not nice and breaks the loop. If the substring is nice, it updates the result if the substring is longer than the current longest nice substring found.