每日一题 0201

(2022.02.01)每日一题 最长的美好子字符串

披着皮的简单题,我看第一眼就停懵,这简单题感觉思路都会超时,就觉得自己太愚蠢,哎,不过也确实。

最后依旧是看官方题解,好家伙!简单题不简单呀。

主要是由于字符串长度较小,可以通过枚举来计算,但是也使用了别的思想,就是二进制压缩的思想,一共26个字母,小写大写的字母可以用两个26位二进制表示。通过遍历所有子串,来计算最长美好字串。若大小写的26位二进制相等,则说明是一个美好字符串。如果一个字母多次出现,会因为大小写的26位二进制相等,但序列长度不同,而更新序列,即可以更新最长序列。

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])) {
                //二进制存储,与字母的ASCII码相差多少位,就左移几位,用以存储字母。
                    lower |= 1 << (s[j] - 'a');
                } else {
                    upper |= 1 << (s[j] - 'A');
                }
                //当两个二进制相等,且序列更大,则更新起始index和长度,当然index可能还是原来的啦
                if (lower == upper && j - i + 1 > maxLen) {
                    maxPos = i;
                    maxLen = j - i + 1;
                }
            }
        }
        return s.substr(maxPos, maxLen);
    }
};

上一篇:Leetcode 1743. 从相邻元素对还原数组(DAY 122) ---- 贪心算法学习期


下一篇:5. 最长回文子串