文章目录
这是简单题？？？数据规模后边加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 ) O(n^3) O(n3)， n n 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
)
O(n^2)
O(n2)。
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
)
O(n^2)
O(n2)。
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 ) O(n) 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 "";
}
};