LeetCode 395. 至少有 K 个重复字符的最长子串--二分查找+前缀和+优先队列

395. 至少有 K 个重复字符的最长子串

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

示例 1：

输入：s = “aaabb”, k = 3
输出：3
解释：最长子串为 “aaa” ，其中 ‘a’ 重复了 3 次。

示例 2：

输入：s = “ababbc”, k = 2
输出：5
解释：最长子串为 “ababb” ，其中 ‘a’ 重复了 2 次， ‘b’ 重复了 3 次。

提示：

1 <= s.length <= 104
s 仅由小写英文字母组成
1 <= k <= 105

题解

很有趣的题目，我们循环从左到右遍历一遍，于是乎，针对当前位置i，我们在区间[i,s.length()]之间找一个位置pos，这个位置pos满足26个字母，在区间[i,pos]内要么没出现过，要么出现次数大于等于k，于是我们可以单独对每个字母进行前缀和，最后用二分查找去优化速度，先单独去找每个字母的这个pos，那么针对每个字母，要么在区间[i,s.length()]内出现次数大于等于k，那么就是小于k，针对小于k这种情况，只能让这个字母不要出现，于是又要二分一次，去找这个finl位置，使得在区间[i,finl]内该字母没出现过。

于是乎我们针对26个字母，每个字母找两个位置finl,finr，使得
在区间[i,finl]内该字母没出现过，在区间[i,finr]内该字母出现次数恰好为k。

如果某个字母找不到这样的finr，那么只能把这个字母剔除，于是当前区间更新为[i,finl]，那么同样的，如果其他的字母的finr是大于当前这个字母的finl，说明会导致其他的字母在区间[i,finl]内是不会出现k次的，于是其他字母也只能删除，更新为其他字母和当前的该字母的finl比较小，看谁小。不断这样的更新区间，为了保证其他字母的finr可以有效被比较到，要使用优先队列，把finr大的排前面先比较，不然容易出现这样的情况。

pos=5

字符’a’，finl=0,finr=5;
字符’b’，finl=1,finr=7;

如果先拿pos和字符’a’的比较，那么不会被更新，pos还是为5，再和字符’b’比较，结果更新答案为pos=1，这样明显不对。

因为当前的pos应该为0，所以说要先把finr大的字母放前面考虑。

AC代码

class Solution {
public:struct Node{int l,r;friend bool operator < (Node a, Node b){return a.r < b.r;//x大的优先}};int sum[10010][26];priority_queue<Node>q;int longestSubstring(string s, int k) {memset(sum,0,sizeof(sum));for(int i=0;i<s.length();i++){for(int j=0;j<26;j++){sum[i+1][j]=sum[i][j]+(s[i]-'a'==j?1:0);}}int res=0;for(int i=1;i<=s.length();i++){bool flag=true;int pos=s.length();for(int j=0;j<26;j++){if(sum[s.length()][j]-sum[i-1][j]==0)//该字符在[i,s.length()]区间不存在，不用考虑continue;int L=i-1,R=s.length(),finr=-1;while(L<=R){int mid=(L+R)/2;if(sum[mid][j]-sum[i-1][j]>=k)//找每个字母出现次数满足大于等于k的位置{R=mid-1;finr=mid;}else L=mid+1;}L=i-1,R=s.length();int finl=-1;while(L<=R){int mid=(L+R)/2;if(sum[mid][j]-sum[i-1][j]<=0)//找到该字符没有出现的位置{L=mid+1;finl=mid;}else R=mid-1;}//cout<if(finr==-1)//说明没找到，那么当前的区间不能包含字母j{pos=min(pos,finl);//当前区间只能小于finl，使得当前的区间不会出现字符jflag=false;//说明当前区间有问题，需要舍去某个字符}else{//没啥问题，把找到的位置储存进去Node t;t.l=finl,t.r=finr;q.push(t);}}if(flag)//没啥问题res=max(res,int(s.length()-i+1));else{while(q.size()>0){if(pos<q.top().r)pos=min(pos,q.top().l);q.pop();}if(pos<i)continue;//cout<//最后所有的字符都满足要求res=max(res,pos-i+1);}}return res;}
};

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