题目描述

解题思路

采用二进制枚举来优化
双重循环遍历字符串，第一重i为左端点，第二重为n - 1;
每次进入第二重前都要将lower(记录小写字母)和upper(记录大写字母)初始化为0
遍历中如果该字母为小写就 进行lower |= 1 << (s[j] - 'a') 大写同理
每一次j循环后如果lower == upper 就更新最大长度

TIPS:假设$x = (1010)_2$ 则 x |= 1 << 2 => $x = (1110)_2$

代码

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);
    }
};