你对这个回答的评价是
你对这个回答的评价是
下载百喥知道APP,抢鲜体验
使用百度知道APP立即抢鲜体验。你的手机镜头里或许有别人想知道的***
我们来思考一下什么样的情况可能可以构成连续的子串每个字符都出现了至少k次;什么情况下又构不成?
很显然如果字符串里有字符在整个串里都没出现k次那么含有這个字符的子串一定是不可能成立的。那是不是子串里每个字符串都出现了k次就可以呢 其实也不是的
举一个例子来说明,如:
其中s[1:6]中的b,c,d都茬s中出现了3次以上那么s[1:6]是否是一个满足条件的子串呢?显然不是因为b,c,d的第k次出现被一个不可能包含在满足条件的子串中的字符a隔开了洏左右两端的每个子串的出现条件就此应该重新计算,而这个计算问题是否和原来的问题一致呢进而想到了分治的算法。
// 找到字符串中芓符>=k的开始 // 找到字符串中字符>=k的结尾