首页 > 其他分享 >2981. 找出出现至少三次的最长特殊子字符串 I

2981. 找出出现至少三次的最长特殊子字符串 I

时间:2024-05-29 22:12:26浏览次数:24  
标签:找出 end idx int 2981 cnt length 字符串

题目描述

给你一个仅由小写英文字母组成的字符串 s 。

如果一个字符串仅由单一字符组成,那么它被称为 特殊 字符串。例如,字符串 "abc" 不是特殊字符串,而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。

返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度,如果不存在出现至少三次的特殊子字符串,则返回 -1 。

子字符串 是字符串中的一个连续 非空 字符序列。

思路

  • 统计每个字母出现时的下标,用vector<vector<int>> cnt(26)记录字母和其对应的下标,cnt[i]为字母,vector<int> idx = cnt[i],idx为该字母下标的集合
  • 遍历cnt中所有字母,找到每个字母出现 至少三次 的 最长特殊子字符串
  • 如果cnt[i].size() < 3,说明该字母出现的次数小于3次,不可能有 至少三次 的最长特殊子字符串,略过
  • 遍历cnt时,先找到cnt[i]的最长特殊字符串length,也就是连续的cnt[i]的长度。接着遍历idx,统计length出现的次数,如果过次数 < 3,length--,重复遍历idx,直到找到 出现至少三次的最长特殊子字符串或者length = 1
  • 比较每一个字母的length,找到最大的

代码

class Solution {
public:
    int maximumLength(string s) {
        int n = s.size();
        vector<vector<int>> cnt(26);

        for(int i = 0;i < n;i++){
            cnt[s[i] - 'a'].push_back(i);
        }

        int maxLength = -1;
        for(int i = 0;i < 26;i++){
            if(cnt[i].size() < 3) continue;

            vector<int> idx = cnt[i];
            int m = idx.size();

            int start = 0,end = 0;
            int length = 0;
            while(end < m){
                if(idx[end] - idx[start] == end - start) end++;
                else{
                    length = max(length,end - start);
                    start = end;
                }
            }
            
            length = max(length,end - start);  
            int count = 0;
            while(length > 1){
                for(int j = 0;j < m;j++){
                    int k = j + length - 1;
                    if(k < m && idx[j] - idx[k] == j - k) count++;
                }
                if(count >= 3) break;
                count = 0;
                length--;
            }

            maxLength = max(maxLength,length);
        }

        return maxLength;
        
    }
};

标签:找出,end,idx,int,2981,cnt,length,字符串
From: https://www.cnblogs.com/EavenWang/p/18221199

相关文章

  • Day 8 | 344.反转字符串 、541. 反转字符串II 、151.翻转字符串里的单词
    344.反转字符串建议:本题是字符串基础题目,就是考察reverse函数的实现,同时也明确一下平时刷题什么时候用库函数,什么时候不用库函数题目链接/文章讲解/视频讲解:https://programmercarl.com/0344.反转字符串.html思考太简单了classSolution:defreverseString(self,......
  • 17.js字符串
    字符串创建1.字面量创建    var字符串名=字符串2.内部构造函数创建    var字符串名=newString('字符串')length属性    只能读取不能设置varstr='abcdfegfgl'console.log(str.length)//10str.length=5......
  • 【leetcode每日一题】——2903. 找出满足差值条件的下标 I——python
    给你一个下标从 0 开始、长度为 n 的整数数组 nums ,以及整数 indexDifference 和整数 valueDifference 。你的任务是从范围 [0,n-1] 内找出  2 个满足下述所有条件的下标 i 和 j :abs(i-j)>=indexDifference 且abs(nums[i]-nums[j])>=valueDi......
  • C# String.Format 数值类型格式化字符串 保留两位小数
    统计学中普遍遵循四舍六入五成双例:32.6752-》32.67例:32.6755-》32.67注:String.Format() .framework4.7.2是四舍五入;.net6.net7则符合四舍六入五成双;其余版本没有进行测试。//.framework4.7.2varDistance=32675;vara=String.Format("{0:N2}",Distance/100......
  • MySQL四种主要的存储引擎,约束条件null not null,严格模式,基本字段类型之整型,浮点型,
    ⅠMySQL之存储引擎【一】什么是存储引擎日常生活中文件格式有很多,并且针对不同的文件格式会有对应不同的存储方式和处理机制针对不同的数据应该有对应的不同的处理机制存储引擎就是不同的处理机制【二】MySQL四种主要的存储引擎【1】Innodb是MySQL5.5版本之后的默认存......
  • lua拼接字符串
    在Lua中,拼接字符串可以使用多种方法,包括使用..操作符、string.format函数,或者使用循环和table.concat函数。下面是一些常见的字符串拼接示例:使用..操作符localpart1="Hello"localpart2="World"localresult=part1..""..part2print(result)--输出"HelloWorld......
  • Java-生成固定长度的随机字符串、随机字符串开头的ID、写入文件、读取文件
    packagecom.sgcc;importjava.io.*;importjava.text.DecimalFormat;importjava.util.ArrayList;importjava.util.List;importjava.util.Random;publicclassMain{publicstaticStringgenerateMixedString(intlength){Randomrandom=ne......
  • python容器,字符串,列表,元组,字典介绍和常规操作
    在Python中,常见容器有:(1)字符串:str(2)列表:list(3)元组:tuple(4)字典:dict#容器#列表[]#list1=[1,2,3,4,5,6,7,8,9]可以增删改查#元组()#tuple1=(1,2,3,4,5,6,7,8,9)只能查,不能改#字典{}#dict1={1:1,2:2,3:3,4:4,5:5,6:6,7:7}#集合{}#set1={1,2,3,4,5,6,7,8,9}......
  • 展示字符串信息加密与解密的过程
    声明:该内容皆为原创,仅供业内人士相互学习交流经验,任何未经授权复制、转载、传播或使用本网站(或应用程序)内容的行为,将受到法律的制裁。如因侵权行为给本网站(或应用程序)或任何第三方造成损失的,侵权人应当承担相应的法律责任)实现编译器:vs2022   编译器建议使用13、19、22等......
  • 力扣:2028. 找出缺失的观测数据
    2028.找出缺失的观测数据现有一份 n+m 次投掷单个 六面 骰子的观测数据,骰子的每个面从 1 到 6 编号。观测数据中缺失了 n 份,你手上只拿到剩余 m 次投掷的数据。幸好你有之前计算过的这 n+m 次投掷数据的 平均值 。给你一个长度为 m 的整数数组 rolls......