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