type
status
date
slug
summary
tags
category
icon
password
题目:最长的美好子字符串
当一个字符串
s
包含的每一种字母的大写和小写形式 同时 出现在 s
中,就称这个字符串 s
是 美好 字符串。比方说,"abABB"
是美好字符串,因为 'A'
和 'a'
同时出现了,且 'B'
和 'b'
也同时出现了。然而,"abA"
不是美好字符串因为 'b'
出现了,而 'B'
没有出现。给你一个字符串
s
,请你返回 s
最长的 美好子字符串 。如果有多个答案,请你返回 最早 出现的一个。如果不存在美好子字符串,请你返回一个空字符串。示例 1:
示例 2:
示例 3:
示例 4:
提示:
1 <= s.length <= 100
s
只包含大写和小写英文字母。
题解
方法一:枚举
思路
关键点:状态压缩
题目要求找到最长的美好子字符串,题目中给定的字符串
s
的长度 length
范围为 1≤length≤100
。由于字符串的长度比较小,因此可以枚举所有可能的子字符串,然后检测该字符串是否为美好的字符串,并得到长度最长的美好字符串。题目关于美好字符串的定义为: 字符串中的每个字母的大写和小写形式同时出现在该字符串中。检测时,由于英文字母
‘a’−‘z’
最多只有 26
个, 因此可以利用二进制位来进行标记,lower
标记字符中出现过小写英文字母,upper
标记字符中出现过大写英文字母。如果满足 lower=upper
,我们则认为字符串中所有的字符都满足大小写形式同时出现,则认定该字符串为美好字符串。题目要求如果有多个答案,返回在字符串中最早出现的那个。此时,只需要首先检测从以字符串索引 0 为起始的子字符串。
附录
- Author:Zinphy
- URL:https://zouysay.cn/article/b4b0b7e6-cd42-4f2c-bf32-78f46ae5e3c4
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!