leetcode 1763 最长的美好子字符串

题意简述

当一个字符串 $s$ 包含的每一种字母的大写和小写形式同时出现在 $s$ 中，就称这个字符串 $s$ 是美好字符串。求出给定字符串 $s$ 最长的美好子字符串。

算法分析

法一 枚举

由于字符只有出现与不出现的区别，与出现次数无关，使用二进制数表示 $26$ 个字母的出现情况。枚举子串左端点，对于给定的某一左端点，顺序枚举右端点，只需 $O(1)$ 时间判断当前子串小写与大写出现情况是否相同。

法二 分治

挖坑

法三 滑动窗口

挖坑

实现代码

法一 枚举

class Solution {
public:
    string longestNiceSubstring(string s) {
        int n = s.size();
        int maxPos = 0;
        int maxLen = 0;
        for (int i = 0; i < n; ++i) {
            int lower = 0;
            int 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);
    }
};

法二 分治

挖坑

法三 滑动窗口

挖坑