Q:

A:

分治，对于字符串s的任何一个字符，如果它的频数（在s中出现的次数）小于k，则它一定不会出现在最后的结果里，也就是从它的位置一劈两半，考察左右。对于当前字符串s，我们先建立字典统计其中每种字符出现的次数，对于某字符，假设为x，x在当前字符串中出现的次数小于为kk，kk<k。则所有的字符x可将当前字符串s切片为kk+1个子串，递归对这kk+1个子串进行考察即可。

class Solution {

public:

    int longestSubstring(string s, int k) {

        return func(s,k,0,s.size()-1);

    }

	int func(const string& s,const int& k,int le,int ri){

		// cout<<le<<" "<<ri<<endl;

		if(le>ri){

			return 0;

		}

		unordered_map<char,int> tmp;

		for(int i=le;i<=ri;++i){

			tmp[s[i]]+=1;

		}

		int last_partition=le-1;

		int res=0;

		for(int i=le;i<=ri;++i){

			if(tmp[s[i]]<k){

				res=max(res,func(s,k,last_partition+1,i-1));

				last_partition=i;

			}

		}

		if (last_partition==le-1){	//没分段

			return ri-le+1;

		}

		else{

			res=max(res,func(s,k,last_partition+1,ri));	//最后一段

			return res;

		}

	}

};

巴特西

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

Q:

A:

最新文章

热门文章