最长的美好子字符串
00 min
2024-7-30
2024-7-30
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 为起始的子字符串。
 
 

附录

 
上一篇
判断二叉树是不是搜索树
下一篇
关键路径