这是简单题？？？数据规模后边加3个0直接玩完…

题目链接

https://leetcode-cn.com/problems/longest-nice-substring/
官方题解

题目描述

当一个字符串 s 包含的每一种字母的大写和小写形式 同时 出现在 s 中，就称这个字符串 s 是 美好 字符串。比方说，"abABB" 是美好字符串，因为 'A' 和 'a' 同时出现了，且 'B' 和 'b' 也同时出现了。然而，"abA" 不是美好字符串因为 'b' 出现了，而 'B' 没有出现。

给你一个字符串 s ，请你返回 s 最长的 美好子字符串 。如果有多个答案，请你返回 最早 出现的一个。如果不存在美好子字符串，请你返回一个空字符串。

示例1

输入：s = "YazaAay"
输出："aAa"
解释："aAa" 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 'a' 和大写形式 'A' 也同时出现了。
"aAa" 是最长的美好子字符串。

示例2

输入：s = "Bb"
输出："Bb" 
解释："Bb" 是美好字符串，因为 'B' 和 'b' 都出现了。整个字符串也是原字符串的子字符串。

示例3

输入：s = "c" 
输出：""
解释：没有美好子字符串。

示例4

输入：s = "dDzeE"
输出："dD"
解释："dD" 和 "eE" 都是最长美好子字符串。
由于有多个美好子字符串，返回 "dD" ，因为它出现得最早。

提示

• 1 <= s.length <= 100
• s 只包含大写和小写英文字母。

题解1

暴力穷举所有的子串，判断每个子串是否是美好字符串。时间复杂度$O(n^3)$，$n$为字符串长度。

代码如下：

class Solution {
public:bool isgood(string &s, int l, int r){bool appear[200] = {false};for(int i=l;i<r;i++)    appear[s[i]] = true;for(char c='a';c <= 'z';c++){if(appear[c] != appear[c + 'A' - 'a'])  return false;}return true;}string longestNiceSubstring(string s) {int maxl = -1;int leftofmax = -1;for(int l=0;l<s.length();l++){for(int r=l+1;r<=s.length();r++){if(r - l > maxl && isgood(s, l, r)){maxl = r - l;leftofmax = l;}}}if(maxl != -1)  return s.substr(leftofmax, maxl);else return "";}
};

实际上，对于小于等于当前最长美好子串长度的子串没必要再验证，因此程序可以优化。

string longestNiceSubstring(string s) {int maxl = -1;int leftofmax = -1;for(int l=0;l<s.length();l++){for(int r=l+maxl+1 ;r<=s.length();r++){if(isgood(s, l, r)){maxl = r - l;leftofmax = l;}}}if(maxl != -1)  return s.substr(leftofmax, maxl);else return "";}

题解2

判断子串是否是美好的方法可以优化：对于一个子串，统计区分大小写和不区分大小写的种类数，如果前者是后者的两倍，那么就是美好字符串，边统计边判断，时间复杂度$O(n^2)$。

class Solution {
public:char lower(char c){if (c >= 'A' && c <= 'Z')   return c - 'A' + 'a';return c;}string longestNiceSubstring(string s) {int maxl = -1;int leftofmax = -1;for(int l=0;l<s.length();l++){int num1 = 0; // 区分大小写的字母种类int num2 = 0; // 不区分大小写的字母种类bool appear1[200] = {false};bool appear2[200] = {false};for(int r=l; r<s.length(); r++){if (!appear1[s[r]]){num1++;appear1[s[r]] = true;}if (!appear2[lower(s[r])]){num2++;appear2[lower(s[r])] = true;}if(r - l + 1 > maxl && num1 == num2 * 2){maxl = r - l + 1;leftofmax = l;}}}if(maxl != -1)  return s.substr(leftofmax, maxl);else return "";}
};

因为只有26个英文字母，所以可以数字二进制每一位表示一个英文字母有没有出现，分别统计大写字母和小写字母的出现情况，代码可以写的更简单，时间复杂度$O(n^2)$。

class Solution {
public:string longestNiceSubstring(string s) {int maxl = -1;int leftofmax = -1;for(int l=0;l<s.length();l++){int lower = 0; // 小写字母出现情况int upper = 0; // 大写字母出现情况for(int r=l; r<s.length(); r++){if(s[r] >= 'a' && s[r] <= 'z')  lower |= (1 << (s[r] - 'a'));else upper |= (1 << (s[r] - 'A'));if(r - l + 1 > maxl && lower == upper){maxl = r - l + 1;leftofmax = l;}}}if(maxl != -1)  return s.substr(leftofmax, maxl);else return "";}
};

题解3(参考自官方题解)

利用分治的思想，对于一个字符串，如果它不是美好的，那么其中一定有一些字母在这个字符串中没有大小写同时出现，可以用这些字母把字符串分割成若干子串，再去判断每个子串中字符出现情况。看题解说时间复杂度可以达到$O(n)$，虽然我不知道为啥。

class Solution {
private:int maxl;int leftofmax;
public:char Lower(char c){if(c >= 'a' && c <= 'z')    return c;return c - 'A' + 'a';}void dfs(string &s, int l, int r){if(r - l > maxl && l > leftofmax){int lower = 0;int upper = 0;for(int i=l;i<r;i++){if(s[i] >= 'a' && s[i] <= 'z')  lower |= (1 << (s[i] - 'a'));else upper |= (1 << (s[i] - 'A'));}if(lower == upper){maxl = r - l;leftofmax = l;return;}int legal = (lower & upper);int p = l;while(p < r){l = p;char lc;while(p < r && (legal & (1 << (Lower(s[p]) - 'a'))))    p++;dfs(s, l, p);p++;}}}string longestNiceSubstring(string s) {maxl = -1;leftofmax = -1;dfs(s, 0, s.length());if(maxl != -1)  return s.substr(leftofmax, maxl);else return "";}
};