When the uppercase and lowercase forms of each letter contained in a string s ， appear in s ， at the same time, the string s ， is called a beautiful string. For example, "abABB" is a beautiful string, because 'a' and 'a' appear at the same time, and 'B' and 'B' appear at the same time. However, "abA" is not a good string because 'B' appears and 'B' does not appear.

Give you a string # s, please return the longest # substring of # s. If there are multiple answers, please return to the one that appears first. If there is no good substring, please return an empty string.

Example 1:
Enter: s = "YazaAay"
Output: "aAa"
Explanation: "aAa" is a beautiful string, because this substring contains only one letter, and its lowercase form 'a' and uppercase form 'a' appear at the same time.
"aAa" is the longest substring.

Example 2:
Input: s = "Bb"
Output: "Bb"
Explanation: "Bb" is a beautiful string because 'B' and 'B' appear. The entire string is also a substring of the original string.

Example 3:
Enter: s = "c"
Output: ''
Explanation: there is no beautiful substring.

Example 4:
Input: s = "dDzeE"
Output: "dD"
Explanation: "dD" and "eE" are the longest substrings.
Because there are multiple substrings, return "dD" because it appears first.

Tips:

• 1 <= s.length <= 100
• s # contains only uppercase and lowercase English letters.

analysis:

Method 1: Enumeration

The simplest way to solve this problem is to enumerate all substrings and record the longest beautiful substring. Substrings with a length less than or equal to the longest beautiful substring do not need to be traversed. For the inspection method, you can define an array with a length of 26 to record all the letters of the string. The lower case is 1, the upper case is 2, and all the letters are 3. Finally, traverse the array without 1 or 2, which is a good substring.

Time complexity: O(n^3)
Space complexity: O(n)

class Solution {
    public String longestNiceSubstring(String s) {
        //Convert string to character array
        char[] cs = s.toCharArray();
        //Record the start and end points corresponding to the maximum length and the modified length
        int max = 0, start = 0;
        //ergodic
        for(int i = 0; i < cs.length; ++i){
            for(int j = cs.length-1; j > i; --j){
                //If the length of the substring is less than the maximum length, terminate this cycle
                if(j - i < max){
                    break;
                }
                //Check whether the substring is a substring
                if(check(cs, i, j)){
                    //Record the new maximum length and start and end points, and terminate the cycle
                    max = j - i + 1;
                    start = i;
                    break;
                }
            }
        }
        return s.substring(start, start+max);
    }

    public boolean check(char[] cs, int start, int end){
        //Create an array representing 26 English letters
        int[] letters = new int[26];
        //Traverses the character at the specified position
        for(int i = start; i <= end; ++i){
            //Make the difference between the current character and 'a', because the uppercase letter is in front of the lowercase letter, the difference between all uppercase letters and 'a' must be negative
            int num = cs[i] - 'a';
            if(num >= 0){
                //If the corresponding position of the letter is 0, it means that the case of the letter does not appear. If the value is 1, it means lower case, 2 means upper case, and 3 means both case
                if(letters[num] == 0){
                    letters[num] = 1;
                }else if(letters[num] == 2){
                    letters[num] = 3;
                }
            }else{
                num = cs[i] - 'A';
                if(letters[num] == 0){
                    letters[num] = 2;
                }else if(letters[num] == 1){
                    letters[num] = 3;
                }
            }
        }
        //Traversal. If the value of the letter contains 1 or 2, it must not be a substring
        for(int i: letters){
            if(i == 1 || i == 2){
                return false;
            }
        }
        return true;
    }
}

Method 2: enumeration + prefix and

Now that enumeration is mentioned, it's easy to think of it Prefix and Because when two substrings make a difference, the letters in the subtracted substring have case, so this substring must be a beautiful substring. Therefore, we can define a two-dimensional array to record the number of each letter contained in all substrings from [0,1] to [0, len -1], and make a difference between each two substrings to record the longest substring.

Time complexity: O(n^2*C)
Space complexity: O(n*C)

class Solution {
    public String longestNiceSubstring(String s) {
        //Record string length
        int len = s.length();
        //If the string length is 1, an empty string will be returned directly
        if(len == 1){
            return "";
        }
        //Define a two-dimensional array to store the number of corresponding letters contained in the string from [0,1] to [0,len-1], and the accii code of z is 128
        int[][] nums = new int[len+1][129];
        //Traversal string
        for(int i = 1; i <= len; ++i){
            //Clone the number of letters in the previous substring
            nums[i] = nums[i-1].clone();
            //Add one to the number of new letters on this floor
            nums[i][s.charAt(i-1)]++;
        }
        //Record the length of the longest substring and the corresponding starting point
        int max_len = 0, start = 0;
        //ergodic
        for(int i = 0; i <= len; ++i){
            for(int j = len; j > i; --j){
                //The difference string is a beautiful substring, and the length is greater than the longest beautiful substring, covering the longest beautiful substring
                if(j - i > max_len && check(nums[i], nums[j])){
                    max_len = j - i;
                    start = i;
                    break;
                }
            }
        }
        return s.substring(start, start+max_len);
    }

    //Check whether the difference string of two substrings is a good substring
    public boolean check(int[] a, int[] b){
        //Traversing lowercase letters, the ascii code of a is 65 and a is 97
        for(int i = 65; i < 97; i++){
            //Record the number of letters in case
            int cap = b[i] - a[i];
            int low = b[i+32] - a[i+32];
            //If both are 0, it means none, if none is 0, it means all. If a single is 0, it means only one returns false
            if((cap == 0 && low != 0) || (cap != 0 && low == 0)){
                return false;
            }
        }
        return true;
    }
}

Method 3: enumeration + bit operation

From method 2, we can know that what we need to judge is whether the case of a substring appears at the same time, regardless of the number of occurrences. Therefore, we can define two numbers: low, cap, low indicates whether lowercase occurs, cap indicates whether uppercase occurs, and 26 letters are represented by 26 bits of binary, When a letter appears, take 1 and move it to the left. Subtract the digits of a or a from the letter and do or operation with low or cap. Such a letter appears repeatedly, and the phase or after it remains the same. When cap and low are equal, the substring is a good substring.

Time complexity: O(n^2)
Space complexity: O(1)

class Solution {
    public String longestNiceSubstring(String s) {
        //Record string length
        int len = s.length();
        //A length of 1 returns an empty string directly
        if(len == 1){
            return "";
        }
        //Record the maximum length and start position
        int max_len = 0, start = 0;
        //ergodic
        for(int i = 0; i < len; ++i){
            //Record the occurrence times of case
            int cap = 0, low = 0;
            for(int j = i; j < len; ++j){
                //Current letter
                char cur = s.charAt(j);
                //Judge case or operation
                //a lowercase letter
                if(cur >= 'a'){
                    low |= (1 << (cur - 'a'));
                }
                //Capitalize
                else{
                    cap |= (1 << (cur - 'A'));
                }
                //Judge whether the case times are the same and the length is greater than the maximum length
                if(cap == low && j - i + 1> max_len){
                    max_len = j - i + 1;
                    start = i;
                }
            }
        }
        return s.substring(start, start+max_len);
    }
}

Method 4: divide and conquer algorithm

It is not difficult to see that when a letter is not capitalized or lowercase, the longest beautiful substring must be on the left or right of the letter. Traverse the string to find the letter, and then cut recursion to take the longest beautiful substring.

Time complexity: O(n*log n)
Space complexity: O(log n)

class Solution {
    public String longestNiceSubstring(String s) {
        //Get string length
        int len = s.length();
        //If the string length is less than 2, an empty string is returned
        if(len < 2){
            return "";
        }
        //ergodic
        for(int i = 0; i < len; ++i){
            //Current letter
            char c = s.charAt(i);
            //If there is no upper or lower case of the letter, the longest substring must be around the letter
            if((c >= 'a' && !s.contains((char)(c - 32) + "")) || (c < 'a' && !s.contains((char)(c + 32) + ""))){
                //Record two substrings
                String s1 = longestNiceSubstring(s.substring(0, i));
                String s2 = longestNiceSubstring(s.substring(i+1, len));
                //Returns the longest substring
                if(s1.length() >= s2.length()){
                    return s1;
                }
                return s2;
            }
        }
        return s;
    }
}

Title Source: LeetCode
Link: https://leetcode-cn.com/problems/longest-nice-substring