1763. 最长的美好子字符串-贪心算法
算法 字符串 最长 贪心 美好
2023-09-14 09:06:52 时间
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” ,因为它出现得最早。
对于这一题,其实,可能很多人都知道怎么做,但是实现起来,需要几个技巧,去方便我们实现算法思想,首先应该设置两个数组去记录字母的出现次数,还有需要在判断是否是美好字符串时设置一个变量去判断,这样实现起来会简单很多,解题代码如下,需要处理的细节也挺多的:
char * longestNiceSubstring(char * s){
int bpha[26];
int spha[26];
for(int i=0;i<26;i++){
bpha[i]=0;
spha[i]=0;
}
int low=0,high=0,r=1;
int index=0;
int max=0;
for(int i=0;s[i]!='\0';i++){
for(int k=0;k<26;k++){
bpha[k]=0;
spha[k]=0;
}
int count=0;
for(int j=i;s[j]!='\0';j++){
if(s[j]>='a'&&s[j]<='z'){
spha[s[j]-'a']++;
if(spha[s[j]-'a']==1&&bpha[s[j]-'a']==0){
count++;
}
if(spha[s[j]-'a']==1&&bpha[s[j]-'a']>=1){
count--;
}
}
else{
bpha[s[j]-'A']++;
if(spha[s[j]-'A']==0&&bpha[s[j]-'A']==1){
count++;
}
if(spha[s[j]-'A']>=1&&bpha[s[j]-'A']==1){
count--;
}
}
if(count==0){
if(j-i+1>max){
index=i;
max=j-i+1;
}
}
}
}
printf("%d %d",index,max);
s[index+max]='\0';
return s+index;
}
相关文章
- [算法系列之十二]字符串匹配之蛮力匹配
- 字符串的匹配算法_多字符串匹配
- JS算法探险之字符串
- Opencv分水岭算法——watershed自动图像分割用法[通俗易懂]
- 日拱算法:双指针解“压缩字符串”
- 每日算法刷题Day13-在O(1)时间删除链表结点、合并两个排序的链表、把字符串转换成整数
- 基于嵌入式端的人脸识别算法
- 《算法竞赛进阶指南》0x15 字符串
- K-近邻算法(KNN)
- ARMA-EGARCH模型、集成预测算法对SPX实际波动率进行预测|附代码数据
- 字符串暴力匹配算法
- Go 数据结构和算法篇(十一):字符串匹配之 BF 算法
- 【Node.js算法题】数组去重、数组删除元素、数组排序、字符串排序、字符串反向、字符串改大写 、数组改大写、字符替换
- 小小码民刷算法——反转字符串
- 算法遇记 | 字符串段拆插问题 - 富文本
- redis 数据删除策略和逐出算法的问题小结
- 算法-旋转字符串-三步翻转法详解编程语言
- 算法-表示数值的字符串详解编程语言
- 算法-时间复杂度为O(n)的排序详解编程语言
- 字符串解码算法详解编程语言
- 找出字符串中的最长回文子串 – 马拉车算法详解编程语言
- Sunday 字符串匹配算法(C++实现)详解编程语言
- C++冒泡排序数据结构、算法及改进算法
- php中最简单的字符串匹配算法