Leetcode 1763. 最长的美好子字符串 (枚举所有子串,状态压缩看字符串是否出现)

Leetcode 1763. 最长的美好子字符串 (枚举所有子串,状态压缩看字符串是否出现)

枚举所有字符子串,然后用状态压缩压缩表示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); 
    }
};

 

上一篇:SpringBoot学习:逆向工程-集合MyBatis


下一篇:MyBatisPlus XML 自定义分页