1763. 最长的美好子字符串

题目描述

当一个字符串 s 包含的每一种字母的大写和小写形式同时出现在 s 中，就称这个字符串 s 是美好字符串。比方说，"abABB" 是美好字符串，因为 'A' 和 'a' 同时出现了，且 'B' 和 'b' 也同时出现了。然而，"abA" 不是美好字符串因为 'b' 出现了，而 'B' 没有出现。

给你一个字符串 s ，请你返回 s 最长的 美好子字符串 。如果有多个答案，请你返回最早出现的一个。如果不存在美好子字符串，请你返回一个空字符串。

示例 1：

1
2
3
4


输入：s = "YazaAay"
输出："aAa"
解释："aAa" 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 'a' 和大写形式 'A' 也同时出现了。
"aAa" 是最长的美好子字符串。

示例 2：

1
2
3


输入：s = "Bb"
输出："Bb"
解释："Bb" 是美好字符串，因为 'B' 和 'b' 都出现了。整个字符串也是原字符串的子字符串。

示例 3：

1
2
3


输入：s = "c"
输出：""
解释：没有美好子字符串。

示例 4：

1
2
3
4


输入：s = "dDzeE"
输出："dD"
解释："dD" 和 "eE" 都是最长美好子字符串。
由于有多个美好子字符串，返回 "dD" ，因为它出现得最早。

提示：

1 <= s.length <= 100
s 只包含大写和小写英文字母。

解法一：枚举

思路

枚举所有子字符串，判断每一个子字符串是否是美好子字符串。

MY CODE

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
public:
    string longestNiceSubstring(string s) {
        pair<int, int> ansIndex{-1, -1};
        int maxLen = 0;
        for (int i = 0; i < s.size() - 1; ++i) {
            for (int j = i + 1; j < s.size(); ++j) {
                if (isWell(s, i, j) && maxLen < j - i + 1) {
                    maxLen = j - i + 1;
                    ansIndex.first = i;
                    ansIndex.second = j;
                }
            }
        }
        return maxLen > 0 ? s.substr(ansIndex.first, ansIndex.second + 1 - ansIndex.first) : "";
    }

private:
    bool isWell(const string &str, int l, int r) {
        unordered_set<char> luSet(str.cbegin() + l, str.cbegin() + r + 1);
        return all_of(luSet.cbegin(), luSet.cend(),
                      [&](char ch) {
                          return ch >= 'a' ? luSet.count(char(ch - 32)) : luSet.count(char(ch + 32));
                      });
    }
};

—

复杂度分析

时间复杂度：O(n^3)，其中n为字符串s的长度。isWell的复杂度为O(n)。空间复杂度：O(n)

Official Answer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


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

—

复杂度分析

时间复杂度：O\left(n^{2}\right) ，其中 n 为字符串的长度。需要枚举所有可能的子字符串，因此需要双重偱环遍历字符串，总共可能有 n^{2} 个连续的子字符串。

空间复杂度： O(1) 。由于返回值不需要计算空间复杂度，除了需要两个整数变量用来标记以外不需要额外的空间。

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/longest-nice-substring/solution/zui-chang-de-mei-hao-zi-zi-fu-chuan-by-l-4l1t/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法二：分治法

MY CODE

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


class Solution {
    string str;
    int maxPos = 0, maxLen = 0;
public:
    string longestNiceSubstring(string s) {
        this->str = s;
        divideAndConquer(0, (int) str.size());
        return str.substr(maxPos, maxLen);
    }

private:
    void divideAndConquer(int start, int end) {
        if (start + 1 >= end)
            return;
        int lower = 0, upper = 0;
        for (int i = start; i < end; ++i) {
            if (islower(str[i]))
                lower |= 1 << (str[i] - 'a');
            else
                upper |= 1 << (str[i] - 'A');
        }
        if (upper == lower) {
            if (end - start > maxLen) {
                maxLen = end - start;
                maxPos = start;
            }
            return;
        }
        int valid = lower & upper;
        int pos = start;
        while (pos < end) {
            start = pos;
            while (pos < end && valid & (1 << (tolower(str[pos]) - 'a'))) {
                ++pos;
            }
            divideAndConquer(start, pos);
            ++pos;
        }
    }
};

复杂度分析

时间复杂度: O(n \cdot|\Sigma|) ，其中 n 为字符串的长度， |\Sigma| 为字符集的大小，本题中字符串仅包含英文大小写字母，因此 |\Sigma|=52 。本题使用了逆归，由于字符集最多只有 \frac{|\Sigma|}{2} 个不同的英文字母，每次逆归都会去掉一个英文字母的所有大小写形式，因此递归深度最多为 \frac{|\Sigma|}{2} 。

—

Official Answer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


class Solution {
    private int maxPos;
    private int maxLen;

    public String longestNiceSubstring(String s) {
        this.maxPos = 0;
        this.maxLen = 0;
        dfs(s, 0, s.length() - 1);
        return s.substring(maxPos, maxPos + maxLen);
    }

    public void dfs(String s, int start, int end) {
        if (start >= end) {
            return;
        }
        int lower = 0, upper = 0;
        for (int i = start; i <= end; ++i) {
            if (Character.isLowerCase(s.charAt(i))) {
                lower |= 1 << (s.charAt(i) - 'a');
            } else {
                upper |= 1 << (s.charAt(i) - 'A');
            }
        }
        if (lower == upper) {
            if (end - start + 1 > maxLen) {
                maxPos = start;
                maxLen = end - start + 1;
            }
            return;
        }
        int valid = lower & upper;
        int pos = start;
        while (pos <= end) {
            start = pos;
            while (pos <= end && (valid & (1 << Character.toLowerCase(s.charAt(pos)) - 'a')) != 0){
                ++pos;
            }
            dfs(s, start, pos - 1);
            ++pos;
        }
    }
}

—

复杂度分析

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/longest-nice-substring/solution/zui-chang-de-mei-hao-zi-zi-fu-chuan-by-l-4l1t/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法三：滑动窗口

MY CODE

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


class Solution {
public:
    string longestNiceSubstring(string s) {
        int maxPos = 0, maxLen = 0;
        auto check = [&](int typeNum) {
            vector<int> lowerCnt(26), upperCnt(26);
            // cnt为[l...r)中同时存在大写和小写形式的字符的数量，total为[l...r)中字符种类数
            int total = 0, cnt = 0;
            for (int l = 0, r = 0; r < s.size(); ++r) {
                int idx = tolower(s[r]) - 'a';
                if (islower(s[r])) {
                    ++lowerCnt[idx];
                    if (1 == lowerCnt[idx] && upperCnt[idx] > 0)
                        ++cnt;
                } else {
                    ++upperCnt[idx];
                    if (1 == upperCnt[idx] && lowerCnt[idx] > 0)
                        ++cnt;
                }
                total += 1 == (lowerCnt[idx] + upperCnt[idx]) ? 1 : 0;
                // 缩小窗口
                while (total > typeNum) {
                    idx = tolower(s[l]) - 'a';
                    if (islower(s[l])) {
                        --lowerCnt[idx];
                        // 注意不能漏掉upperCnt[idx]>0的条件。
                        if (0 == lowerCnt[idx] && upperCnt[idx] > 0)
                            --cnt;
                    } else {
                        --upperCnt[idx];
                        if (0 == upperCnt[idx] && lowerCnt[idx] > 0)
                            --cnt;
                    }
                    ++l;
                    total -= 0 == (lowerCnt[idx] + upperCnt[idx]) ? 1 : 0;
                }

                if (cnt == typeNum && r - l + 1 > maxLen) {
                    maxPos = l;
                    maxLen = r - l + 1;
                }
            }
        };
        int mask = 0;
        for (char ch : s)
            mask |= 1 << (tolower(ch) - 'a');
        for (int i = 1; i <= __builtin_popcount(mask); ++i)
            check(i);
        return s.substr(maxPos, maxLen);
    };
};

复杂度分析

空间复杂度: O(|\Sigma|) 。需要 O(|\Sigma|) 存储所有大小写字母的计数。

Official Answer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60


class Solution {
    private int maxPos;
    private int maxLen;

    public String longestNiceSubstring(String s) {
        this.maxPos = 0;
        this.maxLen = 0;

        int types = 0;
        for (int i = 0; i < s.length(); ++i) {
            types |= 1 << (Character.toLowerCase(s.charAt(i)) - 'a');
        }
        types = Integer.bitCount(types);
        for (int i = 1; i <= types; ++i) {
            check(s, i);
        }
        return s.substring(maxPos, maxPos + maxLen);
    }

    public void check(String s, int typeNum) {
        int[] lowerCnt = new int[26];
        int[] upperCnt = new int[26];
        int cnt = 0;
        for (int l = 0, r = 0, total = 0; r < s.length(); ++r) {
            int idx = Character.toLowerCase(s.charAt(r)) - 'a';
            if (Character.isLowerCase(s.charAt(r))) {
                ++lowerCnt[idx];
                if (lowerCnt[idx] == 1 && upperCnt[idx] > 0) {
                    ++cnt;
                }
            } else {
                ++upperCnt[idx];
                if (upperCnt[idx] == 1 && lowerCnt[idx] > 0) {
                    ++cnt;
                }
            }
            total += (lowerCnt[idx] + upperCnt[idx]) == 1 ? 1 : 0;
            while (total > typeNum) {
                idx = Character.toLowerCase(s.charAt(l)) - 'a';
                total -= (lowerCnt[idx] + upperCnt[idx]) == 1 ? 1 : 0;
                if (Character.isLowerCase(s.charAt(l))) {
                    --lowerCnt[idx];
                    if (lowerCnt[idx] == 0 && upperCnt[idx] > 0) {
                        --cnt;
                    }
                } else {
                    --upperCnt[idx];
                    if (upperCnt[idx] == 0 && lowerCnt[idx] > 0) {
                        --cnt;
                    }
                }
                ++l;
            }
            if (cnt == typeNum && r - l + 1 > maxLen) {
                maxPos = l;
                maxLen = r - l + 1;
            }
        }
    }
}

—

复杂度分析

空间复杂度: O(|\Sigma|) 。需要 O(|\Sigma|) 存储所有大小写字母的计数。

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/longest-nice-substring/solution/zui-chang-de-mei-hao-zi-zi-fu-chuan-by-l-4l1t/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

总结

在java中使用Character.isLowerCase判断某个字符是否是小写字符，在C++中则使用islower。在java中使用Character.toLowerCase将字母转换成小写，则C++中则使用tolower。
STL算法any_of判断某个区间内的元素都满足某个条件，条件常以lambda表达式传递给该函数，如果对所有区间内元素lambda表达式运算结果都为true则结果也为true，反之为false。