枚举所有字符子串,然后用状态压缩压缩表示26个字符,可以在O(1)时间判断是否出现,时间复杂度是O(n^2)
class Solution {
public:
string longestNiceSubstring(string s) {
int maxPos = 0;
int maxLen = 0;
for (int i = 0; i < s.size(); i++) {
int lower = 0, upper = 0;
for (int j = i; j < s.size(); j++) {
if (islower(s[j])) {
lower |= 1 << (s[j] - 'a');
} else {
upper |= 1 << (s[j] - 'A');
}
if (lower == upper && j - i + 1 > maxLen) {
maxPos = i;
maxLen = j - i + 1;
}
}
}
return s.substr(maxPos, maxLen);
}
};