题目描述
解题思路
采用二进制枚举来优化 双重循环遍历字符串，第一重i为左端点，第二重为n - 1; 每次进入第二重前都要将lower(记录小写字母)和upper(记录大写字母)初始化为0 遍历中如果该字母为小写就 进行lower |= 1 << (s[j] - 'a') 大写同理 每一次j循环后如果lower == upper 就更新最大长度
TIPS:假设 则 x |= 1 << 2 =>
代码
cpp
class Solution {
public:
string longestNiceSubstring(string s) {
int n = s.length();
int maxPos = 0;
int maxLen = 0;
for (int i = 0; i < n; i++) {
int lower = 0, upper = 0;
for (int j = i; j < n; 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);
}
};
