对于一个字符串,请设计一个高效算法，找到字符串的最长无重复字符的子串长度。 给定一个字符串A及它的长度n，请返回它的最长无重复字符子串长度。保证A中字符全部为小写英文字符，且长度小于等于500。 测试样例： “aabcb”,5 返回：3
有点类似动态规划，但是比动态规划简单很多，首先利用一个vec记录每个元素位置对应的最长无重复子串，利用map记录每个字符出现的位置，对于一个新的元素位置，如果之前的map中没有记录那么最长子串就是前一个最长字符子串的长度加1，如果有记录，看记录的位置，如果记录的位置在前一个字符最长子串的范围内，则最长子串就是记录位置和当前元素位置之间的元素，如果记录的位置在前一个字符最长子串范围外，那么最长子串就是前一个字符最长子串的长度加1。最后更新字符的记录位置。循环进行处理即可。 代码如下。
class DistinctSubstring {public: int longestSubstring(string A, int n) { if(n<=0) return 0; vector<int> vec(n,0); vec[0]=1; map<char,int> mymap; mymap[A[0]]=0; for(int i=1;i!=n;++i) { if(mymap.find(A[i])==mymap.end()) { mymap[A[i]]=i; vec[i]=vec[i-1]+1; } else { int temp=mymap[A[i]]; if(temp>=i-vec[i-1]) vec[i]=i-temp; else vec[i]=vec[i-1]+1; mymap[A[i]]=i; } } int max=INT_MIN; for(auto c:vec) { if(c>max) max=c; } return max; }};新闻热点
疑难解答
