问题描述
当一个字符串 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 <= 100s 只包含大写和小写英文字母。
解题思路
方法一：枚举
因为也是求区间，所以可以枚举从每一个位置出发最远能够到达的位置。
因为小写字符或者大写字符只有 26 个，所以可以直接使用一个 32 位的整型数字的 \(0-25\) 位来标记某个字符是否出现。这样判断一个子字符串是否是美好子字符串，可以使用两个 32 整型数字 \(a,b\) 来分别标记大小写字符的出现情况，如果 \(a=b\)，说明子字符串是美好子字符串，否则则不是。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution:
def longestNiceSubstring(self, s: str) -> str:
n = len(s)
beg = end = 0
for i in range(n):
k, a, b = i, 0, 0
for j in range(i, n):
if "a" <= s[j] <= "z":
a |= 1 << (ord(s[j]) - ord("a"))
else:
b |= 1 << (ord(s[j]) - ord("A"))
if a == b:
k = j
if k - i > end - beg:
beg, end = i, k
return s[beg : end + 1] if beg != end else ""
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | class Solution {
public:
string longestNiceSubstring(string s) {
int n = s.size();
int beg = 0, end = 0;
for (int i = 0; i < n; ++i) {
int k = i, a = 0, b = 0;
for (int j = i; j < n; ++j) {
if ('a' <= s[j] && s[j] <= 'z') {
a |= 1 << (s[j] - 'a');
} else {
b |= 1 << (s[j] - 'A');
}
if (a == b) {
k = j;
}
}
if (k - i > end - beg) {
beg = i, end = k;
}
}
return beg != end ? s.substr(beg, end - beg + 1) : "";
}
};
|
另一种稍微优化一点的方案是，如果从 \(i\) 位置出发最远能够到达位置 \(k\)，那么下一次遍历就直接可以从 \(k+1\) 开始，因为如果从 \(i+1\) 开始最远不可能到达超过 \(k\) 的位置，否则从 \(i\) 出发也能到达。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution:
def longestNiceSubstring(self, s: str) -> str:
n = len(s)
i = beg = end = 0
while i < n:
k, a, b = i, 0, 0
for j in range(i, n):
if "a" <= s[j] <= "z":
a |= 1 << (ord(s[j]) - ord("a"))
else:
b |= 1 << (ord(s[j]) - ord("A"))
if a == b:
k = j
if k - i > end - beg:
beg, end = i, k
i = k + 1
return s[beg : end + 1] if beg != end else ""
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | class Solution {
public:
string longestNiceSubstring(string s) {
int n = s.size();
int beg = 0, end = 0;
int i = 0;
while (i < n) {
int k = i, a = 0, b = 0;
for (int j = i; j < n; ++j) {
if ('a' <= s[j] && s[j] <= 'z') {
a |= 1 << (s[j] - 'a');
} else {
b |= 1 << (s[j] - 'A');
}
if (a == b) {
k = j;
}
}
if (k - i > end - beg) {
beg = i, end = k;
}
i = k + 1;
}
return beg != end ? s.substr(beg, end - beg + 1) : "";
}
};
|
时间复杂度：\(\mathcal{O}(n^2)\)
空间复杂度：\(\mathcal{O}(1)\)
方法二：分治
如果某个位置不满足条件，则可以将该位置分成左右两部分求解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 | class Solution {
public:
string longestNiceSubstring(string s) {
function<string(int, int)> search = [&] (int beg, int end) -> string {
if (beg >= end) {
return "";
}
int a = 0, b = 0;
for (int i = beg; i <= end; ++i) {
if ('a' <= s[i] && s[i] <= 'z') {
a |= 1 << (s[i] - 'a');
} else {
b |= 1 << (s[i] - 'A');
}
}
int c = a & b;
int split = -1;
for (int i = beg; i <= end; ++i) {
int id = 'a' <= s[i] && s[i] <= 'z' ? s[i] - 'a' : s[i] - 'A';
if (((c >> id) & 1) == 0) {
split = i;
break;
}
}
if (split == -1) {
return s.substr(beg, end - beg + 1);
}
string left = search(beg, split - 1), right = search(split + 1, end);
return left.size() >= right.size() ? left : right;
};
return search(0, s.size() - 1);
}
};
|
时间复杂度：\(\mathcal{O}(n)\)
空间复杂度：\(\mathcal{O}(1)\)