【每日一题】1763. 最长的美好子字符串

1763. 最长的美好子字符串

• 题目描述：
• 解题思路

题目描述：

当一个字符串 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$ 只包含大写和小写英文字母。

解题思路

本次采用分治法+递归的思想。首先我们分析字符串中如果存在一个字符，其对应的大写或小写字母没有出现在字符串中，那么最长的美好子字符串一定不包含该字符，因子最长美好子字符串一定在其左侧或右侧。此时可以递归判断其左侧或右侧的美好子字符串的长度，取最大值即可。

# -*- coding: utf-8 -*-## ----------------------------------------------
# Name:         LongestNiceSubstring.py
# Description:
# Author:       PANG
# Date:         2022/2/2
# ----------------------------------------------
# Leetcode 1763. 最长的美好子字符串
class Solution:def longestNiceSubstring(self, s: str) -> str:if len(s) <= 1:return ""for i, char in enumerate(s):if char.upper() not in s or char.lower() not in s:return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i + 1:]), key=len)return sif __name__ == '__main__':solution = Solution()print(solution.longestNiceSubstring(s="YazaAay"))

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！