1763.最长的美好子字符串

链接：1763.最长的美好子字符串
难度：Easy
标签：位运算、哈希表、字符串、分治、滑动窗口
简介：给你一个字符串 s ，请你返回 s 最长的 美好子字符串 。如果有多个答案，请你返回 最早 出现的一个。如果不存在美好子字符串，请你返回一个空字符串。

题解 1 - cpp

• 编辑时间：2022-02-01
• 执行用时：8ms
• 内存消耗：6.1MB
• 编程语言：cpp
• 解法介绍：遍历所有起点和终点。

class Solution {
   public:
    int arr[256];
    int check(string &str, int start, int end) {
        memset(arr, 0, sizeof(int) * 256);
        for (int i = start; i <= end; i++) {
            arr[str[i]] = 1;
        }
        for (int i = 'A'; i <= 'Z'; i++) {
            if (arr[i] && !arr[i + 32]) return 0;
        }
        for (int i = 'a'; i <= 'z'; i++) {
            if (arr[i] && !arr[i - 32]) return 0;
        }
        return 1;
    }
    string longestNiceSubstring(string s) {
        string ans = "";
        for (int i = 0; i < s.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (check(s, j, i) && i - j + 1 > ans.size())
                    ans = s.substr(j, i - j + 1);
            }
        }
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2022-02-01
• 执行用时：12ms
• 内存消耗：6MB
• 编程语言：cpp
• 解法介绍：遍历所有起点和终点。

class Solution {
   public:
    int arr[26];
    int check(string &str, int start, int end) {
        memset(arr, 0, sizeof(int) * 26);
        for (int i = start; i <= end; i++) {
            if (str[i] >= 'a')
                arr[str[i] - 'a'] |= 0b10;
            else
                arr[str[i] - 'A'] |= 0b01;
        }
        for (int i = 0; i < 26; i++) {
            if (arr[i] != 0 && arr[i] != 3) return 0;
        }
        return 1;
    }
    string longestNiceSubstring(string s) {
        string ans = "";
        for (int i = 0; i < s.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (check(s, j, i) && i - j + 1 > ans.size())
                    ans = s.substr(j, i - j + 1);
            }
        }
        return ans;
    }
};