最长的美好子字符串

难度: Easy

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

Submission

运行时间: 26 ms

内存: 16.0 MB

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        if len(s) < 2:
            return ""
        for i, x in enumerate(s):
            if x.lower() not in s or x.upper() not in s:
                l = self.longestNiceSubstring(s[:i])
                r = self.longestNiceSubstring(s[i+1:])
                return l if len(l) >= len(r) else r
        return s

Explain

这个题解采用了递归的方式来找出最长的美好子字符串。首先，它检查整个字符串是否为美好字符串，即每个在字符串中出现的字符的大写和小写形式都必须同时存在。如果整个字符串是美好的，直接返回整个字符串。如果不是，它找到第一个不满足美好字符串条件的字符，然后将字符串分成左右两部分，在这两部分中递归地寻找最长的美好子字符串。最后，比较左右两部分得到的最长美好子字符串的长度，返回较长的那个。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        if len(s) < 2:  # 如果字符串长度小于2，不能形成美好字符串
            return ""
        for i, x in enumerate(s):  # 遍历字符串
            if x.lower() not in s or x.upper() not in s:  # 检查每个字符的大小写是否同时存在
                l = self.longestNiceSubstring(s[:i])  # 递归左半部分
                r = self.longestNiceSubstring(s[i+1:])  # 递归右半部分
                return l if len(l) >= len(r) else r  # 返回更长的美好子字符串
        return s  # 如果整个字符串是美好的，返回整个字符串

Explore

在检查是否为美好字符串时，通过字符的大写或小写形式在字符串中的存在来判断是一种直观的方法，因为美好字符串的定义是每个字符的大写和小写形式都必须同时存在。更高效的方法可能包括使用位运算或哈希表。例如，可以用一个位向量（整数）来跟踪哪些字母已经以大写或小写形式出现。每个字母对应位向量中的两个位，一个表示小写，一个表示大写。遍历字符串时，更新这些位，最后检查位向量中的相关位对是否都被设置，从而判断是否所有字符都满足美好字符串的条件。这种方法可能在某些情况下比逐个字符检查更快，特别是字符串很长时。

在递归过程中忽略不满足条件的字符是基于这样的事实：如果一个字符的大小写形式不同时存在，那么包含这个字符的任何字符串都不能是美好字符串。因此，将字符串分割成不包含该字符的左右两部分，分别递归寻找各自的最长美好子字符串，是一种合理的策略。这种方法不会忽略可能的更长美好子字符串，因为任何包含不满足条件字符的子字符串本身就不能是美好的。

在这个递归方法中，主要目标是找到最长的美好子字符串，因此比较左右子字符串的长度通常是足够的。如果两个子字符串的长度相同，则由于递归的性质，先处理的（即左侧的）子字符串将被优先返回。因此，在这种情况下，不需要额外考虑它们的起始位置。只有在处理多个长度相同的最长美好子字符串时，才需要考虑返回最早出现的一个，但通常这种情况下返回任何一个都是可接受的。